Heaps

Question 1

Get index of left child, right child and parent of heap

Answer 1

Store heap in array with size of heap and a capacity of array as:

Root at index 0
Left child(i) : 2i+1
Right child(i): 2i+2
parent(i): (i-1)//2

Question 2

Time complexity of min-heapify, insert, delete, build heap, extract min

Answer 2

Min-heapify: O(log n) or O(ht)
Insert (calls heapify up): O(log n)
Extract-min (calls heapify down): O(log n)
Decrease key (calls heapify up): O( log n)
Delete key( dec key + extract min): O( log n)
Build heap (heapify down): O(n) tight analysis

Question 3

Binary heap insert

Answer 3

Add the new node to be inserted at last index a[size-1] then compare its value with its parent and swap if necessary until the whole heap till root is in right order.
Time: O(log(size))

Question 4

Binary heap insert

Answer 4

Add the new node to be inserted at last index a[size-1] then compare its value with its parent and swap if necessary until the whole heap till root is in right order. (heapify this newly inserted element following a bottom-up approach.)

Time: O(log(size))

Question 5

Min Heapify down

Answer 5

heapify fn takes index i of node and then compare its value with its left and right child and swap with the minimum of two if required. If swapping occurs, we need to recursively (or iteratively) follow the same steps for the swapped child until the whole heap is heapified.

Question 6

Extract min

Answer 6

First swap the top min element with the last element a[size-1]. then remove the last element and call min-heapify down on the root. Time: O(log n)

Question 7

Decrease Key on min heap

Answer 7

Given an index, decrease the value of key at that index.
Since we are decreasing a key in min-heap, we only need to compare it with its parents and not its children. Since in a min-heap, the children are already greater than the parent.
Here, we will replace the value with given key and then heapify up like in insert while the heap is heapified.

Time: O(h)

Question 8

Delete key from min heap at a given index

Answer 8

We first replace the value to be deleted at a[i] with -INF. Then we call decrease key on the index. So -INF reaches top. Then we call extract min on root so now -INF is replace with a[size-1] and then it reaches the right position. Time: O(h) + O(h): O(log n)

Question 9

Build heap from array

Answer 9

We first find the bottom-most right-most internal node, then from that node to root we keep on applying min-heapify down on each node. So when you come from a lower level to an upper level, your lower level sub-trees are already heapified.

The bottom-most right-most internal node will be the parent of the last leaf node so we can access it easily by ((size-1)-1)//2.

time: O(n)

Question 10

K sorted array

Answer 10

An element at index i will be in position [i-k,i+k].
Make a min-heap of first (k+1) elements for the array for increasing order sorted output {O (k logk)}. Also, maintain a variable index=0 to keep track of where to insert. At index zero, we should have the minimum element which can lie anywhere form 0 to i+k. Next we run a loop from k+1 to n and keep placing the top element at index and inserting the next array element in the heap (O( n-k) log k).
Then when we reach end of array, our heap will still have k+1 elements. Iteratively take out items from heap and then push in the array (O (log k)).

overall time complexity : O(n+k) log k)

Question 11

Purchasing maximum no of items given sum total

Answer 11

One solution is to sort the array and then get the numbers. Time: O(nlog n)

Better solution: Convert the array into min-heap and then keep extracting min from top until sum is consumed.
Time: O(n) + O(result * log n)

Question 12

Find K largest elements of array

Answer 12

One solution is to sort the array and then get the k numbers. Time: O(nlog n) + O(k) := O(n log n)

Better solution: Build max heap of all elements and then take out k items from top.
Time: O(n + klogn)

Best solution: Build min heap of k elements and iteratively compare the next element in the array with the top of the heap, if it is greater than top, insert it. This way at each step the heap will contain the k max elements encountered so far.
Time: O(k + (n-k)log k)

Question 13

Merge K Sorted Arrays

Answer 13

One solution is to put all elements in one result array and sort. Time: O(nk log nk)

Naive solution: Merge two arrays at a time and put in a result array and do that for k arrays.
Time: O(nk^2)

Better solution: Use min heap. Build a k size heap with first elements of each array. In each node store [value, array index, element index in array]. Now keep extracting min element and put in a result array. Each time insert next element from currently extracted array.
Time: O(nk log k)

Question 14

Find Median in a Stream

Answer 14

One solution is to maintain a temp sorted array to find median at any point of time. Time: O(n^2) insertion is O(n).

Another solution is to use augmented BST to maintain elements in sorted order. To find median we can use the same idea as finding kth smallest element by maintaining the number of values smaller to it in each node. Time: O(n log n)

Better solution: We maintain data in 2 halves. First half stores the lower half elements in a max heap while the second greater half elements are maintained in a min heap. if both heaps are of same size, we store the next elements in the first half. Time: O(n log n)
Advantage: heap is cache friendly.