Heapsort: build-heap in O(n), heapify, extract-max

0 · Recall Warm-up

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

• Worst case of quicksort with last-element pivot? from Lesson 3.2.2
• Children of node i in a 1-based heap? from Lesson 0.2.2
• Θ(Σ h/2ʰ)? from Lesson 0.1.2

1 · The Hook

🎣

A max-heap hands you its largest element in O(1). Remove it, fix the heap in O(log n), repeat n times: the elements come out in sorted order. That is heapsort: Θ(n log n) even in the worst case, and in-place. The surprise is that building the heap first costs only Θ(n).

2 · Predict First

🤔

Turn A = [5, 2, 9, 1, 7, 3] into a max-heap by "sifting down" the internal nodes from the last one (position 3, 1-based) back to the root. What is the resulting array?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

Node 3 (9) ≥ its child 3: no change. Node 2 (2) < child 7: swap → [5, 7, 9, 1, 2, 3]. Node 1 (5) < child 9: swap → [9, 7, 5, 1, 2, 3] (2 swaps).

Sift down (heapify) at node i

Compare A[i] with its children; if a child is larger, swap with the larger child and continue from there. Cost O(height of i).

Build-heap (bottom-up)

Sift down every internal node from ⌊n/2⌋ down to 1.

• Nodes near the bottom are many but cheap; the root is costly but alone. Σ over heights h of (n/2ʰ⁺¹ nodes × h) ≤ n·Σ h/2ʰ⁺¹ = O(n).
• (Building by n successive insertions costs O(n log n) in the worst case.)

Heapsort

build_max_heap(A);
for (end = n; end >= 2; end--) {
    swap(A[1], A[end]);        // max goes to its final place
    sift_down(A, 1, end - 1);  // restore the heap on A[1..end-1]
}

• n − 1 extractions × O(log n) = Θ(n log n) in every case (best and worst).
• In-place (O(1) extra), not stable.

Extract-max on the predict heap

[9, 7, 5, 1, 2, 3]: move the last element (3) to the root → [3, 7, 5, 1, 2]; 3 < 7: swap → [7, 3, 5, 1, 2]; 3's children 1, 2 are smaller: stop. Heap [7, 3, 5, 1, 2].

Checking a heap

An array is a max-heap iff A[⌊i/2⌋] ≥ A[i] for every i ≥ 2.

4 · Visual

Build-heap on [5, 2, 9, 1, 7, 3]   (positions 1..6)

        5                  5                  9
      /   \              /   \              /   \
     2     9    ->      7     9    ->      7     5
    / \   /            / \   /            / \   /
   1   7 3            1   2 3            1   2 3
  sift node 2 (2<->7)          sift node 1 (5<->9), then 5 vs 3: stop

5 · Worked Examples

Example 1 Easy

Is [10, 8, 9, 4, 7, 9, 2] a max-heap?

Solution

Check parents: 10 ≥ 8, 9; 8 ≥ 4, 7; 9 ≥ 9, 2. Yes.

Example 2 Medium

Build-heap on [4, 1, 3, 2, 16, 9, 10, 14, 8, 7]. Resulting array?

Solution

[16, 14, 10, 8, 7, 9, 3, 2, 4, 1] (7 swaps).

Example 3 GATE

Time to build a binary max-heap from n unsorted elements by the bottom-up method, and to then find the 5 largest elements by 5 extractions?

Solution

Build Θ(n); 5 extractions O(5 log n) = O(log n); total Θ(n).

6 · GATE Traps

⚠️

• Bottom-up build-heap is Θ(n), not n log n.
• Sift down swaps with the larger child.
• Heapsort is Θ(n log n) even on sorted input; it is not stable.
• 1-based heap formulas; translate to 0-based (children 2i + 1, 2i + 2) if the question does.

7 · Memory Hook

🧠

"Build in linear, extract n times in log."

8 · Connect the Dots

Chapter 3.2 is complete: merge sort, quicksort and heapsort, all Θ(n log n) on average. Chapter 3.3 asks whether any comparison sort can do better (no), how non-comparison sorts do, and how to select the k-th element without sorting.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT1 markBuild swaps

Build-heap (bottom-up) on [5, 2, 9, 1, 7, 3]. Number of swaps?

Numerical answer: ________

Q2MCQ1 markExtract max

Max-heap [9, 7, 5, 1, 2, 3]. After one extract-max, the heap is:

• (A) [7, 3, 5, 1, 2]
• (B) [7, 5, 3, 1, 2]
• (C) [3, 7, 5, 1, 2]
• (D) [7, 2, 5, 1, 3]

Q3NAT2 marksBuild result

Build-heap on [12, 3, 9, 14, 8, 6, 1, 5]. Which element ends at position 2 (1-based)?

Numerical answer: ________

Q4MSQ2 marksHeapsort facts

Which are true?

• (A) Heapsort is stable.
• (B) Heapsort is in-place.
• (C) Bottom-up heap construction is Θ(n).
• (D) Heapsort is Θ(n log n) in the worst case.

Q5MCQ1 markHeap check

Which array is a max-heap?

• (A) [20, 15, 18, 16, 12]
• (B) [15, 20, 18, 10, 12]
• (C) [20, 18, 15, 19, 10]
• (D) [20, 15, 18, 10, 12]

10 · Rule Card

• Sift down: swap with the larger child until in place.
• Build-heap bottom-up from ⌊n/2⌋ to 1: Θ(n). Repeated insertion: O(n log n).
• Heapsort: build, then n − 1 × (swap root with last, sift down): Θ(n log n) all cases; in-place; not stable.
• Max-heap check: A[⌊i/2⌋] ≥ A[i].

11 · Concept Ledger

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

sift down (heapify)bottom-up build-heap Θ(n)heapsortextract-max traceheap-property check

12 · Answer Vault