A Common-Sense Guide to Data Structures and Algorithms, Second Edition, 2nd Edition

Heap Deletion

The first thing to know about deleting a value from a heap is that we only ever delete the root node. This is right in line with the way a priority queue works, in that we only access and remove the highest-priority item.

The algorithm for deleting the root node of a heap is as follows:

1. Move the last node into where the root node was, effectively removing the original root node.

2. Trickle the root node down into its proper place. I’ll explain how trickling down works shortly.

Let’s say we’re going to remove the root node from the heap.

In this example, the root node is the 100. To delete it, we overwrite the root by placing the last ...