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 it down a level (swapping with the better 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 removal is $\Omicron(\lg n)$ since we need at most one swap on each heap level on the path from the root node to the deepest level.