Questions On Heap

I would highly recommend to read below posts before getting into questions on heap-

Questions On Heap

Let’s discuss some of the questions on heap which can be easily solved with the help of Heap.


Problem 1: Find the largest k numbers (in value) out of n numbers. For example, if given an array with ten numbers {1, 8, 9, 2, 10, 14, 3, 4, 7, 16 }, please return the largest five numbers 8, 10, 9, 14, 16.

This Question can also be asked as-
Describe an algorithm to find the largest 1 million numbers in 1 billion numbers. Assume that the computer memory can hold all one billion numbers.
If large numbers involved in problem – first try to solve the problem for smaller numbers.

The simple solution is to sort the n input numbers in descending order and get the first K numbers. Sorting will cost you O(nlogn) time. You can apply insertion sort for smaller number of elements.

We can achieve this in O(nlogk) time using minHeap (Parent is smaller than its children).

  1. Create a Min Heap with the first K numbers.
  2. For each remaining number, insert it in the Min Heap and then delete the minimum value from the heap.
  3. The heap now contains the largest K numbers.
  4. This algorithm is O(n log K), where K is the number of values we are looking for.

The Solution using MinHeap will work as follows.

  • If the K is greater than the number of input elements- no need to do anything just return the elements
  • Fill the Min Heap with K elements of input Array. For example if K=5 then the Min Heap will contain [1, 2, 9, 8, 10]. Now compare the Array[K+1] say N with top element of Min Heap, if N is greater than Heap top element- remove top element and insert N. Repeat the process up to Array.length. Finally you will have the Min Heap with K largest elements.

Let’s create a Min Heap:

Create a class LargestNumbersFinder:

If you are asked to find least k numbers then use Max Heap in similar fashion. Just change the condition if (maxHeap.getMax() > input[i])

Problem 2: You are given a set of integers in an unordered binary tree. Use an array sorting routine to transform the tree into a heap that uses a balanced binary tree as its underlying data structure.

This problem is very simple. You have an unordered binary tree means there is no specific relationship between parent and child like in Binary search tree.
One important property of sorted array is the it satisfy heap condition without calling heapify. If array is sorted in ascending order, it satisfy the Min Heap property and if sorted in Descending order, it satisfy the Max Heap property. You can give try- write some numbers on notepad in sorted order and see if it also satisfy heap condition or not.

Now in this problem, our job is to traverse the Binary tree and store it in an Array- then sort the array in ascending order – now we know that sorted array elements can be directly inserted to min heap. We have already seen that in Array if the parent index is i then left child will be at position 2*i+1 and right child will be at position 2*i+2. Using this relationship insert the array elements back to the Binary tree.

Problem 3: Numbers are randomly generated and passed to a method. Write a program to find and maintain the median value as new values are generated.

First let’s understand about Median
Median is nothing but the middle most element in a set or ordered data. The condition here is that the data should be sorted either in ascending or descending.

For Example:
CASE-I: If number of elements(N) in data set is ODD then the Median = ((N+1)/2)th element in data set.
Data set = {2,5,8,9,10,12,18,20,24,28,26}
In above data set N = 11 which id ODD and (N+1)/2 = (11+1)/2 = 6, therefore Median= 6th element = 12
CASE-II: If number of elements(N) in data set is EVEN then the Median = AVERAGE of (N/2)th and ((N/2)+1))th element in data set.
Data set = {2,5,8,9,10,12,18,20,24,28,26,30}
In above data set N = 12 which id EVEN and N/2 = 12/2 = 6 and (N/2)+1) = 6+1=7 therefore Median= Average of 6th and 7th elements = (12 + 18)/2 = 15

The above problem can be easily solved using two priority heaps: a max heap for the values below the median, and a min heap for the values above the median.
questions on heap

If both the heap size is equal then the Median will be the average of top element of MaxHeap and MinHeap, otherwise the Median will be the top element of larger heap.
When a new value arrives it is placed in the below heap if the value is less than or equal to the median, otherwise it is placed into the above heap. The heap sizes can be equal or the below heap has one extra. This constraint can easily be restored by shifting an element from one heap to the other. The median is available in constant time and updates are O(lg n).

Here I will use Java PriorityQueue collection since it doesn’t have size constraint.


Problem 4: Convert Max-Heap to Min-Heap or vice-versa.

This question I leave as an exercise for the reader. The logic is very simple- If you have to convert Max-Heap to Min-Heap – just call minHeapify(i) for i= (heapSize-1)/2 to 0. And for Min-Heap to Max-Heap call maxHeapify(i) in similar manner.



References:

  • Cracking The Coding Interview- Gayle Laakmann McDowell
  • Programming Interviews Exposed- John Mongan, Eric Giguère, Noah Kindler.
  • Coding Interviews- Harry He