🔼 Insertion in Heap Tree (Min or Max Heap)

Follow Me

Definition:
Insertion in a Heap Tree involves adding the new element at the end (last level, left to right), and then heapifying up (also called "bubble-up") to restore the heap property.

📌 Steps for Insertion (Max Heap Example)

1. Insert at the end of the heap (maintain complete binary tree property).

2. Compare with the parent:

   • If it violates the heap property (e.g., child > parent in Max Heap), swap.

3. Repeat until the heap property is restored.

📊 Basic Diagram (Insert 60 into Max Heap)

Before Insertion:

50 / \ 30 40 / \ 10 20

Insert 60 → Add at last position:

50 / \ 30 40 / \ / 10 20 60

Heapify-Up (60 > 40) → Swap:

50 / \ 30 60 / \ / 10 20 40

Heapify-Up (60 > 50) → Swap:

60 / \ 30 50 / \ / 10 20 40