Remove Operation

Consider we have the following min-heap:

To remove the best, that is to remove the minimum element, we can replace the root with the last element of the heap.

Then, we will delete the last element.

Finally, we restore the heap property by percolating the new root down. This process is often called sink down. It involves comparing the added element with its children and moving the added element down a level (swapping with the smaller of the two children) if needed.

The process is repeated until the children are smaller than or equal to the percolating (sinking) element.

Or, until the percolating (sinking) element reaches the deepest level.

Similar to insertion, the worst-case runtime for remove is $O(\lg n)$ since we need at most one swap on each level of a heap on the path from the root node to the deepest level.