Build-heap and heap sort

ACompressed recap

🧾

Bottom-up build-heap sifts down indices ⌊n/2⌋ − 1 … 0 and costs O(n); inserting keys one by one costs O(n log n) and may give a different heap. Heap sort builds a max-heap, then repeatedly swaps the root to the end of the shrinking heap and sifts down: O(n log n) always, in place, not stable.

BMerged rule card

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

• 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).

CInterleaved GATE-style questions

Q1MCQ2 marksBuild

Bottom-up build-max-heap on 12 7 1 9 4 15 3 8 gives:

• (A) 15 9 12 7 4 1 3 8
• (B) 15 12 9 8 7 4 3 1
• (C) 15 9 12 8 4 1 3 7
• (D) 15 12 9 7 4 1 3 8

Q2NAT1 markSwaps

How many swaps does bottom-up build-max-heap make on 1 2 3 4 5 6 7?

Numerical answer: ________

Q3MCQ1 markCost

Inserting n keys in increasing order one by one into an empty max-heap costs:

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

Q4MCQ2 marksSort pass

After build-heap, 90 80 70 40 45 50 35. After the first pass of heap sort (swap and sift-down), the array is:

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

Q5MSQ2 marksFacts

Which are true?

• (A) Build-heap processes nodes from the last internal node towards the root.
• (B) Leaves need no sift-down in build-heap.
• (C) Two heaps of n keys can be merged in O(n).
• (D) Heap sort is O(n) on already sorted input.

Q6NAT2 marksMin-heap

Bottom-up build-min-heap on 50 20 40 10 30 5 15. What key ends at index 2?

Numerical answer: ________

Q7MCQ1 markSpace

Extra memory used by heap sort (besides the array) is:

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

Q8MCQ2 marksOutput

What is the first line printed?

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) 35 40 45 50 70 80 90
• (B) 40 80 35 90 45 50 70
• (C) 90 80 70 40 45 35 50
• (D) 90 80 70 40 45 50 35

DAnswer Vault