After inserting an element to a Heap, sometimes, the heap’s heap-order property might be broken. In order to fix this, we apply bubbling to that newly inserted element. Heap Bubbling comes in two flavors: up-heap and down-heap.
Up-Heap
This operation has three steps:
- Compare the value of the element with parent’s if parent’s value is greater (for min-heaps), switch those two nodes.
- Repeat step 1 until the heap-order proprty is not broken.
Down-Heap
Down-Heap bubbling is basically the reverse of Up-Heap, when the heap-order property of a heap is broken due to a node that is not a leaf, you need to apply down-heap bubbling. It has two steps:
- Compare the node with both its children, if it is greater than either of its children(for a min heap),switch it with the smallest of its children.
- Repeat step 1 until the property is restored.