🔄 Heapify in Heap Tree

Follow Me

Definition:
Heapify is the process of converting a binary tree or array into a valid heap (Max Heap or Min Heap) by ensuring the heap property is maintained.

There are two types of heapify:

• Heapify-Up (after insertion)

• Heapify-Down (after deletion or bulk heap creation)

📌 When is Heapify Used?

• After inserting a new element (heapify-up)

• After deleting the root element (heapify-down)

• Converting an unsorted array into a heap (bottom-up heapify)

🧱 Basic Diagram: Max Heapify-Down Example

Given array: [30, 50, 60, 10, 20]
We want to apply heapify-down starting from index 0:

Step 1: Start at index 0

30 / \ 50 60 / \ 10 20

Step 2: Compare with children (50, 60) → Largest is 60

Swap 30 with 60:

60 / \ 50 30 / \ 10 20

✅ Max Heap property is restored.

🧠 Python Code for Heapify (Heapify-Down)

def heapify(arr, n, i):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2

    # Compare with left child
    if left < n and arr[left] > arr[largest]:
        largest = left

    # Compare with right child
    if right < n and arr[right] > arr[largest]:
        largest = right

    # Swap if needed and recurse
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

# Example
arr = [30, 50, 60, 10, 20]
heapify(arr, len(arr), 0)
print("After Heapify:", arr)

Output:

After Heapify: [60, 50, 30, 10, 20]

📝 Summary Table

Operation	Direction	When to Use
Heapify-Up	Bottom to Top	After Insertion
Heapify-Down	Top to Bottom	After Deletion or Bulk Build
Time Complexity	O(log n) (one node) / O(n) (full array)