Which of the following insertion sequences will produce the

Which of the following insertion sequences will produce the binary heap shown below? 4 7 2 5 1 7 4 2 5 1 5 1 4 2 7 1 5 2 7 4 None of the above

Solution

d) 1 5 2 7 4

so, here is how it works:

In the given heap, last element to be added has to 5,4 or 1. why? Because new element is added to end at bottom level of heap, and then propagated up. option for 5 is not given. It can\'t be 1, because had it been 1, then 4 would have been root of heap before 1 is added ( from how heap turned out to be finally ) and that is not possible given 2 at right of root.

So, correct option has to be either d or e

Let us try option d, and we can very easily see that this very binary heap turns out. Note that multiple insertion sequences can lead to same final heap, thus heap--> order, might not get the answer in options, and hence we are trying order--> heap.