Problem Solving: Sort an Array By Frequency

Understand Heaps by solving a popular interview problem in python

In Coding Interviews we do not create a heap data structure from scratch, instead, we use a library function to implement heap. In Python heap is implemented using the heapq library. At the end of this article, using this heapq library we will solve a popular interview problemSort an array based on its frequency”.

Photo by Glenn Carstens-Peters on Unsplash

Heaps typically use an array-based data structure, which solves various problems in optimal time. Few Problems where Heap Data Structure is used are:

  1. Finding Minimum or Maximum element in an array
  2. Finding Median in a stream of numbers
  3. Find Kth Largest or Kth Smallest element in an array

Heaps are of two types: Max-Heap and Min-Heap. In Java, both min-heap and max-heap is implemented using a Priority Queue, But in python, the implementation is a bit different as Python’s heapq module does not have built-in support for the max heap but there is a trick to implement max heap.

Min Heap in Python

import heapqarr = [1,5,10, 9, 3]heapq.heapify(arr)// To push an element to heap use heappush(heap_array,element)
// Display the first 3 minimum elements of the array
for i in range(3):
// Output : 1,2,3

Max Heap in Python

Implementing max heap is a little tricky because heapq doesn’t have built-in support that sorts the elements based on maximum element first. By default heapq implements min-heap.

The trick here is to convert the array into negative elements and push it to the heap as shown in the code below

import heapqli = [1,5,10, 9, 3,2]arr=[]
for i in range(len(li):

// Display the first three aximum elements in the array
for i in range(3):
// Output: 10,9,5

Sort an array based on its frequency

Problem Statement: Given an array with repeated elements, Print distinct elements sorted based on its frequency.


Input: [15,8,6,7,6,10,9,7,8,7]
Output: 7 8 6 15 10 9


import heapqarr = [15,8,6,7,6,10,9,7,8,7]heap=[]
// Create a dictionar to store the frequency of elements
for i in arr:
if i in d:
// Push a tuple of frequency and array element
// The heap is sorted based on the first element of tuple
for i,j in d.items():
// nlargest function returns the first n largest numbers of heap
for i,j in result:
print(j,end=" ")

Heap is an important data structure for problem-solving in coding interviews and competitive programming. Thank you for reading, I hope this article was useful for you.


  1. Geeks For Geeks:
  2. Wikipedia:
  3. Python Documentation:

Self-taught Developer | Tech & Self Help Blogger | Exploring Life and Tech | Aim to Help Upcoming Software Developers in their Journey