Generally speaking, we do not delete any node from a heap. The node to remove from a heap is usually the root of the heap. Let us assume the serial number of the last leaf in a heap is n.
The deletion process starts with saving the value of the root node (for returning). Then, the value of node n is copied as the value of the root. The serial number of the last leaf becomes n − 1.
After this is done, the root most likely is not greater than or equal to all its children. If that is the case, then we choose the child with the maximum value and swap the values of that child and the root.
We then perform this operation again with the child that just got its value swapped with the root. This process terminates when there is no need to swap the value of a node and one of its children.
The logic to remove a value (that of the root node) from a heap is illustrated in listing 2.
| Listing 2: | heapremove |
In the worst case, removing the root from a heap is a Θ(log(n)) operation, where n is the number of items in the heap.