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”.

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

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

Sort an array based on its frequency

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

Example:

Solution:

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:

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

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

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store