Heap insertion (sift-up) and deleting the root (sift-down)

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

• Where is the minimum of a max-heap? from Lesson 5.1
• Which node replaces a BST node with two children on deletion? from Lesson 4.5.3
• What is the minimum height of a binary tree with n nodes? from Lesson 4.2.2

1 · The Hook

🎣

A new employee joins at the bottom of the chart; if they outrank their boss, they swap places, again and again, until they sit under someone more senior. When the CEO leaves, the most junior person is put in the top chair temporarily and keeps stepping down below the stronger of the two people under them until order is restored.

2 · Predict First

🤔

Insert 95 into the max-heap 100 80 90 50 60 70 40 30 20. Where does 95 end up? Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

It is placed at index 9 (the next free slot), then swaps with its parent 60, then with 80, and stops under 100: 100 95 90 50 80 70 40 30 20 60. 95 ends at index 1.

Insert: sift-up

Put the new key in the next free position (index n), keeping the tree complete. Then, while it is larger than its parent, swap it with the parent. At most one comparison and swap per level: O(log n).

Delete the root: sift-down

Save the root, move the last element to the root and shrink n. Then, while the moved key is smaller than its larger child, swap it with that larger child. Up to two comparisons per level: O(log n).

C implementation

int h[20], n = 0;                       /* max-heap in h[0..n-1] */

void swap(int *a, int *b) { int t = *a; *a = *b; *b = t; }

void insert(int x)                       /* sift-up */
{
    int i = n++;
    h[i] = x;
    while (i > 0 && h[(i - 1) / 2] < h[i]) {
        swap(&h[i], &h[(i - 1) / 2]);
        i = (i - 1) / 2;
    }
}

void siftDown(int i)
{
    int l, r, big;
    for (;;) {
        l = 2 * i + 1;
        r = l + 1;
        big = i;
        if (l < n && h[l] > h[big]) big = l;
        if (r < n && h[r] > h[big]) big = r;
        if (big == i) return;
        swap(&h[i], &h[big]);
        i = big;
    }
}

int deleteMax(void)
{
    int top = h[0];
    h[0] = h[--n];                       /* last element to the root */
    siftDown(0);
    return top;
}

void show(void) { int i; for (i = 0; i < n; i++) printf("%d ", h[i]); printf("\n"); }

int main(void)
{
    int a[] = {40, 80, 35, 90, 45, 50, 70}, i;
    for (i = 0; i < 7; i++) insert(a[i]);
    show();
    printf("removed %d\n", deleteMax());
    show();
    return 0;
}

Output

90 80 70 40 45 35 50 
removed 90
80 50 70 40 45 35

After deleting 90, the last key 50 moves to the root, swaps with the larger child 80, and stops at index 1 because it is larger than both its new children 40 and 45.

Other operations

4 · Visual

After inserting 95: it rose 9 → 4 → 1.

After deleting 100 from the original heap: 20 moved to the root and sank 0 → 2 → 5.

delete max from 100 80 90 50 60 70 40 30 20

step 1: save 100, move last (20) to the root   20 80 90 50 60 70 40 30
step 2: children 80, 90 -> larger is 90; swap  90 80 20 50 60 70 40 30
step 3: children 70, 40 -> larger is 70; swap  90 80 70 50 60 20 40 30
step 4: index 5 has no children: stop

Sift-down always swaps with the larger child (max-heap).

5 · Worked Examples

Example 1 Easy

Insert 40, 80, 35, 90, 45, 50, 70 one by one into an empty max-heap. Final array?

Solution

90 80 70 40 45 35 50 (the program above prints the same line).

Heap built by 7 insertions.

Example 2 Medium

Max-heap 25 14 16 13 10 8 12. Insert 15, then delete the maximum. Final array?

Solution

Insert: 15 at index 7, swaps with 13 then with 14: 25 15 16 14 10 8 12 13. Delete 25: the last key 13 goes to the root and swaps with the larger child 16; at index 2 its children 8 and 12 are smaller, so it stops. Result: 16 15 13 14 10 8 12.

Example 3 GATE

In a max-heap of height h, what is the maximum number of key comparisons for (a) one insertion, (b) one deletion of the root?

Solution

(a) h (one comparison with the parent per level). (b) 2h (compare the two children, then the larger child with the key, per level). Both O(log n).

6 · GATE Traps

⚠️

• Insertion goes to the next free index, never directly to the correct place.
• Sift-down swaps with the LARGER child in a max-heap (smaller in a min-heap); swapping with the other child breaks the order.
• Deletion moves the LAST element to the root, not a child.
• Deletion uses up to two comparisons per level, insertion one.
• Repeated inserts and a single build (Lesson 5.3) can give different arrays.

8 · Memory Hook

🧠

“New hires bubble up; the replacement CEO sinks under the stronger deputy.”

9 · Connect the Dots

Lesson 5.2 maintained a heap one key at a time, so building a heap of n keys by inserting costs O(n log n). Next lesson answers: can an unsorted array be turned into a heap faster, and how can a heap put an array in increasing order without a second array?

10 · Self-Test

GATE format. Try every question before opening the vault.

Q1MCQ1 markDelete

When deleting the root of a heap, which element is moved to the root first?

• (A) the larger child of the root
• (B) the smallest element
• (C) the last element of the array
• (D) the root’s left child

Q2MCQ2 marksOutput

What does this print?

int h[20], n = 0;                       /* max-heap in h[0..n-1] */

void swap(int *a, int *b) { int t = *a; *a = *b; *b = t; }

void insert(int x)                       /* sift-up */
{
    int i = n++;
    h[i] = x;
    while (i > 0 && h[(i - 1) / 2] < h[i]) {
        swap(&h[i], &h[(i - 1) / 2]);
        i = (i - 1) / 2;
    }
}

void siftDown(int i)
{
    int l, r, big;
    for (;;) {
        l = 2 * i + 1;
        r = l + 1;
        big = i;
        if (l < n && h[l] > h[big]) big = l;
        if (r < n && h[r] > h[big]) big = r;
        if (big == i) return;
        swap(&h[i], &h[big]);
        i = big;
    }
}

int deleteMax(void)
{
    int top = h[0];
    h[0] = h[--n];                       /* last element to the root */
    siftDown(0);
    return top;
}

void show(void) { int i; for (i = 0; i < n; i++) printf("%d ", h[i]); printf("\n"); }

int main(void)
{
    int a[] = {40, 80, 35, 90, 45, 50, 70}, i;
    for (i = 0; i < 7; i++) insert(a[i]);
    show();
    printf("removed %d\n", deleteMax());
    show();
    return 0;
}

• (A) 90 80 70 40 45 35 50, removed 90, 80 50 70 40 45 35
• (B) removed 90 only
• (C) 90 80 70 40 45 35 50, removed 90, 80 70 50 40 45 35
• (D) 40 80 35 90 45 50 70, removed 40, 80 35 90 45 50 70

Q3NAT2 marksInsert

Into the max-heap 100 80 90 50 60 70 40 30 20 the key 95 is inserted. At which 0-based index does 95 end up?

Numerical answer: ________

Q4NAT1 markComparisons

A max-heap has 31 keys (height 4). What is the maximum number of comparisons for one insertion?

Numerical answer: ________

Q5MSQ2 marksDelete

Delete the maximum from 100 80 90 50 60 70 40 30 20. Which are true afterwards?

• (A) 20 ends at index 5.
• (B) The root is 90.
• (C) 80 moves to the root.
• (D) The array has 8 keys.

11 · Rule Card

• Insert: place at index n; sift-up (swap with parent while larger); ≤ h comparisons.
• Delete max: root ← last; n−−; sift-down (swap with larger child while smaller); ≤ 2h comparisons.
• Both O(log n).
• Increase key → sift-up; decrease key → sift-down (max-heap).

12 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

sift-upsift-downheap insertiondelete root

13 · Answer Vault