heap down

Introduction

In Data Structures, a Heap is a special tree-based structure that follows two rules:

1. It is a Complete Binary Tree

2. It follows the Heap Property

   • Max Heap → Parent ≥ Children

   • Min Heap → Parent ≤ Children

When this heap property is violated after deleting an element, we use a process called Heapify Down to fix it.

This blog explains Heapify Down clearly using both
Tree representation and Array representation together.

---

What is Heapify Down?

Heapify Down (also called Sift Down) is the process of:

• Moving an element downwards

• By comparing it with its children

• And swapping it with the correct child

• Until the heap property is restored

It is mainly used after deleting the root element.

---

When Do We Use Heapify Down?

Heapify Down is applied when:

• The root element is removed

• The last element is moved to the root

• This movement breaks the heap property

---

Example: Heapify Down in a Max Heap

Initial Max Heap

Array Representation

Index:  0   1   2   3   4
Array: [50, 30, 40, 10, 20]

Tree Representation

            50
          /    \
        30      40
       /  \
     10   20

The heap property is satisfied.

---

Step 1: Delete the Root

The root element 50 is removed.

To maintain the Complete Binary Tree,
the last element (20) is moved to the root.

Updated Array

[20, 30, 40, 10]

Updated Tree

            20   ❌
          /    \
        30      40
       /
     10

The heap property is now violated because:

20 < 30 and 20 < 40

So we apply Heapify Down.

---

Step 2: Heapify Down (First Level)

Array Index Calculation

Parent index = 0 → 20
Left child   = 2*0 + 1 = 1 → 30
Right child  = 2*0 + 2 = 2 → 40

The largest child is 40.

Swap Operation (Array)

Before: [20, 30, 40, 10]
After : [40, 30, 20, 10]

Same Swap in Tree

            40
          /    \
        30      20
       /
     10

Now, move down to index 2.

---

Step 3: Heapify Down (Second Level)

At index 2:

• There are no children

• Heap property is satisfied

Heapify Down stops.

---

Final Heap After Heapify Down

Final Array

[40, 30, 20, 10]

Final Tree

            40
          /    \
        30      20
       /
     10

The heap is now valid again.

---

Why Do We Move the Last Element to the Root?

This is a very common interview question.

• A heap must always be a Complete Binary Tree

• Removing the root creates a gap

• Moving the last element to the root:

  • Keeps the tree complete

  • Allows heapify down to restore order

---

Tree and Array Relationship in Heap

A heap is stored in an array using these formulas:

Left child  = 2*i + 1
Right child = 2*i + 2
Parent      = (i - 1) / 2

These formulas help convert between tree view and array view.

---

Time Complexity

• Heapify Down: O(log N)

• Because the element moves at most one level per step

---

Heapify Down vs Heapify Up

---

Key Takeaway

Heapify Down restores the heap property by repeatedly swapping a node with its correct child until the structure becomes a valid heap again.