data-structurestheorymax-heap

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.

    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:

    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