Down-heap bubbling

Down-heap bubbling: after replacing the root element with the entry with key $k$ of the last node, the heap-order property may be violated. The algorithm down-heap restores the heap-order property by swapping the entry with key $k$ along a downward path from the root (swap the entry with key $k$ with its child with the smallest key). Down-heap terminates when key $k$ reaches a leaf or a node whose children have keys greater than or equal to $k$. Since the heap has a height $O(\log n)$, down-heap runs in $O(\log n)$ time.