Up-heap bubbling

Up-heap bubbling: After the insertion of a new entry with key $k$, the heap-order property may be violated. The algorithm up-heap restores the heap-order property by swapping entry with the key $k$ along an upward path from the insertion node. Up-heap terminates when the entry with key $k$ reaches the root or a node whose parent has a key smaller than or equal to $k$. Since the heap has a height $O(\log n)$, up-heap runs in $O(\log n)$ time.