List all the keys that could have been the last key inserted in a Max heap

         30 
       /     \
     25       20
    /  \      / \
   22   18   17 16
  /  \  / \  /\
21   13 15 5 2 1

Above is a Max-heap created following a sequence of inserting and removing operations. If we assume that the last operation was an insertion. What will be the possible keys that could have been the last key inserted?

I'm really confused about how we can answer the question and the justification behind the solution.

If someone could give me an explanation of the solution, I would really appreciate it. Thank you!

Solution

A heap has both the completeness and the heap property.

completeness property: All levels of the tree are full, except the last, which is filled from the left
heap property: every parent is greater in value than its children

An insert works by appending the new value to the bottom left, so we don't violate the completeness property.

Now we have to check if the value we just added violates the heap property (i.e. its parent is smaller than it). If so we swap them. We do this until we do not violate the heap property anymore or we have reached to root.

Given your example the following inserts could have happened:

Insert(1) - we are done, no heap violation, possible
Insert(17) - we insert 17, then swap with 1, but 1 is smaller than 2, so 1 could not be a parent, not possible
Insert(20) - we insert 20, swap with 1, then swap with 17, but the first swap means 1 was a parent of 2, so not possible
Insert(30) - you get the idea

Thus the answer is only Insert(1)

Hope this helps. Also, please have a look at the Wikipedia article: https://en.wikipedia.org/wiki/Heap_(data_structure)#Implementation