Find the last element inserted into the min heap?

Question

I am looking at this challenge:

Consider the min-heap [15, 27, 33, 39, 66, 39, 47, 58, 51], built by repeatedly inserting values into an empty heap. Which element could not have been the last element inserted into this heap?

I know an element is inserted from the leaf, but that leaf element takes position according to its value and this makes me confused.

I have made the corresponding binary tree:

How can I determine which values could not have been inserted last?

Answer 1

An insertion into a heap takes these steps:

• Append the value to the end of the array
• Swap that value with its parent if it is less than its parent
• Repeat the swap step for the parent until the heap property is confirmed.

So the inserted value may end up somewhere along the path from "last" leaf to root.

In this case the tree is:

            15
          //   \
         27     33
        // \   /  \
       39  66 39  47
      / \\
     58  51

The "last" leaf is 51, and the path to the root has been marked with double lines. So the candidates for the last insertion are 15, 27, 39 and 51.

For instance, if we assume for a moment that 15 was inserted last, then the tree would have to have looked like this before the insertion (the asterisk denotes the insertion point):

            27
          //   \
         39     33
        // \   /  \
       51  66 39  47
      /  
     58  *

The inserted 15 would swap its way along the double-marked path up to the root. No other node is involved with this operation.

Conclusion: The elements that could not have been inserted last are thus: 33, 66, 39, 47, and 58.

A little warning

We should verify that the tree -- before the insertion -- would be a valid heap. It is always the case with the above example, but if we would have the question for this tree (notice the change in the bottom layer):

            15
          //   \
         27     33
        // \   /  \
       39  66 39  47
      / \\
     51  58

... then the only possible value that could have been inserted last is 58. This is because it is not possible that, before the insertion happened, 58 would have been the parent of 51. That would violate the heap property. And therefore it could not have been swapped down to move an inserted value up.

This scenario has as characteristic that a value on the path is greater than its direct sibling (58 is greater than 51 in this modified example).

However, this "problem" does not occur in the example tree for any of the values 15, 27, 39 or 51: they are all less than their siblings (if they have one).