When removing the top element of a heap, can't we shift every element by 1?


#1

Question

In the context of this exercise, when removing the top element of a heap, can’t we just shift every element by 1 to the left?

Answer

No, this is because shifting all the elements in the list to the left by 1 index can mess up the heap property.

For example, say we had the min-heap
[None, 2, 4, 15, 6, 7, 16]

After we remove the top element, 2, let’s shift each element by 1 index to the left. This gives us
[None, 4, 15, 6, 7, 16]

We can check that this is no longer a valid min-heap, because in a min-heap, the parent elements must be less than or equal to their child elements. In the array, the element 15 at index 2 is larger than its child element 7, at index 4.