Heap Removal
The remove() operation of a heap is extremely important -- usually, the reason why we keep the items in a heap is so that we can efficiently remove them when ready.
The removal algorithm is quite similar to the insertion algorithm, in the sense that we will need to do some sifting to keep the heap in order. However, this time we'll be sifting down instead of sifting up.
Algorithm
Watch the video below to see how to remove the maximum item from a heap:
To summarize, when removing the maximum item from the heap, we can:
- Make a copy of the largest item
- Move the last item in the heap to the root
- "Sift down" the new root item until it is >= its children (or it's a leaf)
- Note: when a parent is less than both of its children, we need to swap the parent with the greater of the two children.
- Return the largest item
Efficiency
Rather than discuss the efficiency explicitly, let's put your analytical skills to the test: