Q129: kth largest element in a heap

Heap is a tree based data structure which follows relative ordering between nodes, specifically either the parent nodes are always greater than their children (called max-heap) or parent nodes are always lesser than their children (called min-heap). Checkout example in question #20 and #21.

Question #129: At what level(s) will the kth largest element be present? (Assume k<n)

Options:

1. Levels 1 to k-1
2. Levels 1 to last level
3. Levels k-1 to last level
4. Levels 1 to min(k-1, last level)

Solution: The correct answer is 4. kth largest element could be present in level 1, in that case all the larger elements will be present in the other subtree of the root node. Also, it could be present at level 2 as a child of 2nd largest element too. Similarly, it can be present at all levels upto k-1. Now, since heap is a full binary tree where all levels are completely filled except the last, there can only be log(n+1) levels. So depending upon where k is lesser than the last level or not, kth element could be present anywhere between levels 1 and min(k-1, last level).

Q120: Optimal way to build a heap?

Question #120: How much time will it take to build a min heap using an optimal solution?

Options:

1. O(n log(n) )
2. O(n)
3. O(n²)
4. O(log(n))

Solution: There are multiple ways to build a heap. First is – we insert element one by one. Insertion in a heap take log(n) steps, and if we insert ‘n’ elements one by one, it becomes O(n log(n)). The other technique is – just build a complete binary tree first of the elements in any order. Then, starting from the nodes at last level, traverse upwards and heapify that node by placing it to the appropriate position in the heap formed till now. For example, if we have elements in the following order:

23, 19, 2, 12, 31, 4, 3, 7, 20

Then as the first step, we can just build a complete binary tree by inserting elements as follows:

 

The leaf nodes 7 and 20 are trivially a heap. Going upwards, we need to heapify 12 and place it at the correct position. Since we are forming a min-heap, 12 would be replaced by the smaller of its two children, hence the next step modifies the heap as follows:

Similarly, nodes 31, 4 and 3 are trivially a heap. Going upwards one more step, 19 would be placed at the correct position and can traverse till the leaf node. The next step modifies the heap as follows:

This can be continued till the root node. And the final heap that will be formed will look like following:

The complexity to build a heap using this technique would be O(n). Hence, the correct answer is option 2.

 

 

Q116: Time to insert a new element in a heap

Min Heap: A min heap is a data structure such that all nodes are less than or equal to its children, and the shape is a complete binary tree. An example of min heap is as follows:

Question #116: How much time will it take to insert a new element in the heap?

Options:

• O(n log (n))
• O(n)
• O(log(n))
• O(log (log(n))

Solution: We always want the heap to be a complete binary tree, hence we would insert it as the next element which would always keep the heap as complete. We would first insert the new element (let’s say “1”) as following:

Next, we would heapify this newly inserted element by moving this element upwards. Hence, after the next step, heap would look like as following:

In the worst case, it can move up till the root, which in this case will. The final heap after moving the newly inserted element at correct position would look like as follows:

Hence, in the worst case, the element would need to be moved log(n) steps, that is, the height of the heap. Hence, the correct answer is option 3.