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

Q21: Last but one element in Max-heap

This is in continuation with our previous question (#20).

Question #21: At what level will the next to smallest element be present in a binary max-heap?

Options:

1. Last level only

2. Last or second last level only

3. Depends on the number of levels

4. Depends on the total number of nodes

Solution: The correct answer is 2. Keeping in mind that heap is a full binary tree except the last level, we can see that the next to smallest element can only have 1 child – i.e. the smallest element. Therefore it can only be present at second last level in that case, otherwise it will be present on the last level.

Q20: Third largest element in a Binary 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). Below is an example of a binary max-heap.

Question #20: Consider the root to be at level 0, root’s children at level 1, and so on. Clearly, the root represents the largest key in the heap (100 in the example above). At what level in a binary max-heap will the 3rd largest key will always be found?

Options:

1. Level 1

2. Level 2

3. Levels 1 or 2

4. Could be anywhere

Solution: The second largest key will always be found in level 1, since it’s children have to be lesser than itself. The third largest key can either be found in level 1 (as the other child of the root) or it can be found in level 2 (as one of the child of the 2nd largest key). Hence the correct option is the 3rd one.