# 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 problem** “ Sort an array based on its frequency”**.

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

- Finding Minimum or Maximum element in an array
- Finding Median in a stream of numbers
- 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)

heapq.heappush(arr,2)// Display the first 3 minimum elements of the array

for i in range(3):

print(heapq.heappop(arr))// 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=[]

k=3for i in range(len(li):

arr.append(-li[i])

heapq.heapify(arr)// Display the first three aximum elements in the array

for i in range(3):

print(-(heapq.heappop(arr)))// 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.

**Example:**

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

Output: 7 8 6 15 10 9

**Solution:**

import heapqarr = [15,8,6,7,6,10,9,7,8,7]heap=[]

heapq.heapify(heap)

d={}// Create a dictionar to store the frequency of elements

for i in arr:

if i in d:

d[i]+=1

else:

d[i]=1// Push a tuple of frequency and array element

// The heap is sorted based on the first element of tuplefor i,j in d.items():

heapq.heappush(heap,(j,i))// nlargest function returns the first n largest numbers of heap

result=heapq.nlargest(len(heap),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.

# References:

- Geeks For Geeks: https://www.geeksforgeeks.org/min-heap-in-python
- Wikipedia: https://en.wikipedia.org/wiki/Heap_(data_structure)
- Python Documentation: https://docs.python.org/3/library/heapq.html