Build-heap in O(n) vs n insertions; heap sort

0 · Recall Warm-up

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

• How many comparisons can deleting the root of a heap of height h take? from Lesson 5.2
• What do rotations in an AVL tree preserve? from Lesson 4.6
• Which abstract type serves the highest priority element first? from Lesson 3.3.3

1 · The Hook

🎣

To organise a new office of 1000 people, you could hire them one at a time, each bubbling up the chart. Or you could seat everyone first, then fix each small team from the bottom up: most people are near the bottom and barely move. The second way is linear time.

2 · Predict First

🤔

Turn 40 80 35 90 45 50 70 into a max-heap in place, sifting down from the last internal node back to the root. Is the result the same as inserting the keys one by one (90 80 70 40 45 35 50)? Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

No. Bottom-up build gives 90 80 70 40 45 50 35. Both are valid heaps; the methods differ.

Bottom-up build-heap

Leaves are already heaps. Sift down every internal node, from the last one (index ⌊n/2⌋ − 1) back to the root. When a node is sifted down, both its subtrees are already heaps.

Cost: a node at height k sinks at most k levels; there are about n/2ᵏ⁺¹ nodes at height k, so the total is n·Σ k/2ᵏ⁺¹ ≤ n: O(n). Building by n insertions costs O(n log n) in the worst case (e.g. increasing keys, each rising to the root).

Heap sort

Build a max-heap (O(n)). Then n − 1 times: swap the root (current maximum) with the last element of the heap, shrink the heap by one and sift the new root down (O(log n)). The array ends in increasing order. Total O(n log n) in every case, with O(1) extra space (in place). Heap sort is not stable: equal keys can change their relative order.

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

void siftDown(int a[], int n, int i)     /* max-heap of size n */
{
    int l, r, big;
    for (;;) {
        l = 2 * i + 1;
        r = l + 1;
        big = i;
        if (l < n && a[l] > a[big]) big = l;
        if (r < n && a[r] > a[big]) big = r;
        if (big == i) return;
        swap(&a[i], &a[big]);
        i = big;
    }
}

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

int main(void)
{
    int a[] = {40, 80, 35, 90, 45, 50, 70}, n = 7, i;
    for (i = n / 2 - 1; i >= 0; i--)     /* build-heap: last internal node down to the root */
        siftDown(a, n, i);
    show(a, n);
    for (i = n - 1; i > 0; i--) {        /* heap sort */
        swap(&a[0], &a[i]);              /* current maximum to its final place */
        siftDown(a, i, 0);               /* heap shrinks to a[0..i-1] */
    }
    show(a, n);
    return 0;
}

Output

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

Trace of the sorting phase

4 · Visual

Start: internal nodes 2, 1, 0 are sifted down in that order.

After build-heap (4 swaps).

build-heap on 40 80 35 90 45 50 70   (n = 7, internal nodes 2, 1, 0)

i = 2:  35 vs children 50, 70 -> swap with 70   40 80 70 90 45 50 35
i = 1:  80 vs children 90, 45 -> swap with 90   40 90 70 80 45 50 35
i = 0:  40 vs children 90, 70 -> swap with 90   90 40 70 80 45 50 35
        40 vs children 80, 45 -> swap with 80   90 80 70 40 45 50 35

Bottom-up: each sift-down works on two subtrees that are already heaps.

5 · Worked Examples

Example 1 Easy

Apply bottom-up build-min-heap to 50 20 40 10 30 5 15.

Solution

5 10 15 20 30 40 50 (swaps: 40↔5, 20↔10, 50↔5, 50↔15).

Example 2 Medium

What does this print?

int swaps = 0;

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

int main(void)
{
    int a[] = {1, 2, 3, 4, 5, 6, 7}, i;
    for (i = 7 / 2 - 1; i >= 0; i--) siftDown(a, 7, i);
    printf("%d %d %d\n", a[0], a[6], swaps);
    return 0;
}

Solution

Build-heap on 1 … 7: i = 2 swaps 3↔7, i = 1 swaps 2↔5, i = 0 swaps 1↔7 then 1↔6. Array 7 5 6 4 2 1 3; 4 swaps.

Output

7 3 4

Example 3 GATE

What is the time to merge two max-heaps of n keys each into one heap of 2n keys?

Solution

Concatenate the two arrays (O(n)) and run build-heap on 2n keys: O(n). Inserting one heap’s keys into the other one by one would be O(n log n).

6 · GATE Traps

⚠️

• Build-heap is O(n), not O(n log n); n insertions are O(n log n) in the worst case.
• Build-heap starts at index ⌊n/2⌋ − 1 (0-based) and goes down to 0, not from the root.
• Build and repeated insertion can produce different heaps from the same input.
• Heap sort with a max-heap gives increasing order; it is O(n log n) in best, average and worst case.
• Heap sort is in place but not stable.

8 · Memory Hook

🧠

“Build from the bottom, sort from the top.” Build: sift down from the last parent to the root (O(n)). Sort: swap root to the end, shrink, sift down (O(n log n)).

9 · Connect the Dots

You now have every heap operation and its cost. GATE questions combine them in tricks: how many different heaps exist, where the k-th largest can sit, heaps with more than two children. Next lesson answers: what are the fastest methods for these heap puzzles?

10 · Self-Test

GATE format. Try every question before opening the vault.

Q1MCQ1 markBuild cost

The tightest bound for bottom-up build-heap on n keys is:

• (A) O(n²)
• (B) O(log n)
• (C) O(n log n)
• (D) O(n)

Q2MCQ2 marksOutput

What does this print?

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

void siftDown(int a[], int n, int i)     /* max-heap of size n */
{
    int l, r, big;
    for (;;) {
        l = 2 * i + 1;
        r = l + 1;
        big = i;
        if (l < n && a[l] > a[big]) big = l;
        if (r < n && a[r] > a[big]) big = r;
        if (big == i) return;
        swap(&a[i], &a[big]);
        i = big;
    }
}

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

int main(void)
{
    int a[] = {40, 80, 35, 90, 45, 50, 70}, n = 7, i;
    for (i = n / 2 - 1; i >= 0; i--)     /* build-heap: last internal node down to the root */
        siftDown(a, n, i);
    show(a, n);
    for (i = n - 1; i > 0; i--) {        /* heap sort */
        swap(&a[0], &a[i]);              /* current maximum to its final place */
        siftDown(a, i, 0);               /* heap shrinks to a[0..i-1] */
    }
    show(a, n);
    return 0;
}

• (A) 90 80 70 40 45 35 50 then the sorted array
• (B) the input, then the sorted array
• (C) 90 80 70 40 45 50 35 then 35 40 45 50 70 80 90
• (D) the sorted array twice

Q3NAT2 marksBuild

Build-max-heap (bottom-up) on 5 3 17 10 84 19 6 22 9. What key is at index 1?

Numerical answer: ________

Q4MSQ1 markHeap sort

Which are true of heap sort?

• (A) O(n log n) worst case
• (B) uses a max-heap to sort in increasing order
• (C) in place (O(1) extra space)
• (D) stable

Q5NAT1 markStart index

Bottom-up build-heap on a 0-based array of 25 keys starts sifting down at which index?

Numerical answer: ________

11 · Rule Card

• Build-heap: for i = ⌊n/2⌋ − 1 down to 0, sift-down(i); O(n).
• n inserts: O(n log n) worst case; may give a different heap.
• Heap sort: build, then n − 1 × (swap root with last, shrink, sift-down); O(n log n), in place, not stable.
• Merging two heaps: concatenate + build: O(n).

12 · Concept Ledger

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

build-heap (bottom-up)heap sortO(n) build vs O(n log n) insertsin-place, not stable

13 · Answer Vault