Bottom-up heap building and heapsort
Connection and contract
The existing “Binary min-heaps: complete shape and safe operations” lesson teaches insertion and extract-min. Reuse its complete-tree shape and sift operation; this lesson adds bottom-up construction and sorting rather than repeating those operations. Here use a max-heap in zero-based A[0:n], with children 2i+1,2i+2 and heap size h. Every parent key is at least its children's keys.
1. Build from the bottom
Indices floor(n/2) through n−1 are leaves and already heaps. For i=floor(n/2)−1 down to 0, sift A[i] down inside size n, choosing the larger child. Before processing i, both child subtrees are heaps. Sifting repairs the only possible violations along the chosen downward path, leaving the whole subtree at i a heap. Reverse index order establishes the invariant; arbitrary top-down sift-down does not.
A sift-down contract: while 2i+1<h, let c be the larger existing child; if A[i]>=A[c], stop; otherwise swap A[i],A[c] and set i=c. Equal children may be resolved consistently either way. Only indices below h belong to the active heap.
Worked build [1,4,3,2,5]: start i=1, children 2 and 5, swap 4 with 5: [1,5,3,2,4]. At i=0 swap 1 with 5: [5,1,3,2,4]; then swap 1 with 4: [5,4,3,2,1]. A max-heap is only partially ordered: sibling order is not constrained and a heap array need not be sorted.
2. Why construction is linear
Bounding every node by O(log n) gives a valid but loose O(n log n). Most nodes are near the bottom. The number at height h is at most O(n/2^(h+1)), and their individual sift cost is O(h+1). Thus total is O(n sum from h=0 to log n of (h+1)/2^(h+1))=O(n), because the infinite series converges. Visiting Θ(n) internal nodes gives Ω(n) for this implementation, hence Θ(n) build time. Repeated insertion is a different construction and has O(n log n) worst-case time.
3. Sorting with a shrinking boundary
Build a max-heap. For end=n−1 down to 1: swap A[0],A[end]; set heap size h=end; sift index 0 down inside A[0:h]. Before each iteration the prefix is a max-heap; the suffix is sorted ascending and contains the largest already removed keys. Moving the remaining maximum to end extends the suffix. Never sift into that suffix.
On the built [5,4,3,2,1], swap 5 to the end and repair: [4,2,3,1 | 5]. Next: [3,2,1 | 4,5]. Next: [2,1 | 3,4,5]. Final: [1 | 2,3,4,5]. The bars mark heap boundaries, not array elements. A max-heap produces ascending order by this process; a min-heap with the same endpoint scheme produces descending order.
4. Costs and traps
Worst-case total time Θ(n log n): linear build plus n−1 extractions each at most logarithmic, with worst-case inputs attaining the bound. Using iterative sift-down gives O(1) auxiliary array storage and no recursive stack. Standard heapsort is unstable: [2a,2b,1] is already a max-heap; successive swaps can yield [1,2b,2a]. Equal keys need not preserve order.
Do not confuse linear build with linear sorting, or repeated insertion with bottom-up build. A heap invariant is weaker than sorted order. Height is distance down to a leaf; depth is distance from the root, and using depth in the build summation gives the wrong intuition.
Original practice: six single-correct MCQs
These original teaching questions are not previous-year questions. Choose exactly one answer.
P01. Last internal index of a zero-based heap of size 10?
A. 4 B. 5 C. 9 D. 10
Answer: A
A: floor(10/2)−1=4.
B: Index 5 is a leaf.
C: Index 9 is a leaf.
D: Index 10 is outside the array.
P02. Bottom-up build worst-case time?
A. Θ(log n) B. Θ(n) C. Θ(n log n) D. Θ(n²)
Answer: B
A: There are linearly many nodes to process.
B: Weighted height sum is linear.
C: O(n log n) is a loose upper bound, but Θ(n log n) is not the tight running time.
D: No quadratic work is needed.
P03. Bottom-up max-heap build of [1,4,3,2,5] gives:
A. [1,2,3,4,5] B. [5,4,3,2,1] C. [5,1,3,2,4] D. [4,5,3,2,1]
Answer: B
A: This is not a max-heap.
B: The stated sift sequence gives this.
C: Node 1 still violates child 4.
D: Root 4 is smaller than child 5.
P04. After moving maximum to A[end], repair which indices?
A. 0 through end B. 0 through end−1 C. end through n−1 D. All n always
Answer: B
A: Includes the sorted suffix entry.
B: New heap size is end.
C: Suffix is already final.
D: This can disrupt sorted entries.
P05. Iterative in-array heapsort auxiliary space?
A. Θ(1) B. Θ(log n) C. Θ(n) D. Θ(n²)
Answer: A
A: Only constant index and swap storage is used.
B: No recursive stack is needed.
C: No output buffer is needed.
D: No matrix is allocated.
P06. Which property is not guaranteed by standard heapsort?
A. Ascending output from max-heap scheme B. Worst-case O(n log n) C. Preserving equal-record order D. Constant extra array storage
Answer: C
A: The sorted suffix invariant gives ascending output.
B: This worst-case bound holds.
C: Swaps may reverse equal records.
D: Iterative sift supports constant auxiliary storage.
Sources and scope
Aligned to the 2026 course. This lesson covers the stated slice, not the entire Algorithms syllabus. All numerical examples and questions are original. No claim of 2027 completeness.
Sign in to keep your progress. Sign in