Remove Operation
Consider we have the following min-heap:
![](/img/20/heap03.png)
To remove the best, that is, to remove the minimum element, we can replace the root with the last element of the heap.
![](/img/20/heap07.png)
Then, we will delete the last element.
![](/img/20/heap08.png)
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 smaller of the two children) if needed.
![](/img/20/heap09.png)
The process is repeated until the children are smaller than or equal to the percolating (sinking) element.
![](/img/20/heap10.png)
Or until the percolating (sinking) element reaches the deepest level.
![](/img/20/heap11.png)
Similar to insertion, the worst-case runtime for removal is $O(\lg n)$ since we need at most one swap on each heap level on the path from the root node to the deepest level.