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.
Bytes of the day 