# 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

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

### Tree Representation

```plaintext
            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

```plaintext
[20, 30, 40, 10]
```

### Updated Tree

```plaintext
            20   ❌
          /    \
        30      40
       /
     10
```

The heap property is now violated because:

```plaintext
20 < 30 and 20 < 40
```

So we apply **Heapify Down**.

---

## Step 2: Heapify Down (First Level)

### Array Index Calculation

```plaintext
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)

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

### Same Swap in Tree

```plaintext
            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

```plaintext
[40, 30, 20, 10]
```

### Final Tree

```plaintext
            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:

```plaintext
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

| Heapify Up | Heapify Down |
| --- | --- |
| Used after insertion | Used after deletion |
| Moves element upward | Moves element downward |
| Compares with parent | Compares with children |

---

## 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.