Question bank — Heap sort — O(n log n), in-place, not stable

False. The heap property only says parent ≥ children, a local rule. Siblings can be in any order, so e.g. [9, 3, 8, 1, 2, 7] is a valid heap but not sorted.

True. If every parent ≥ its children, then by chaining that inequality up any path, the root dominates every node — it is the global maximum.

False. The minimum is always a leaf (a node with no children can't be forced down by a parent), but it can be any leaf, not necessarily the last one.

False. Swapping the root to the back and sifting reorders equal keys unpredictably; e.g. two 5's can have their relative order flipped, so heap sort is not stable.

False. Every sift-down costs at most $O(\log n)$ because a complete tree has height $\lfloor {\log }_{2}n\rfloor$, and we do $O(n)$ of them — so all cases (best, average, worst) are $O(n\log n)$.

False. All swaps happen inside the one array; the tree is implied by index formulas, never materialised. So it is in-place, using only $O(1)$ extra space.

False. Naïvely it looks like $n$ sift-downs × $\log n$, but most nodes are near the bottom with tiny subtrees. Summing the real work gives $O(n)$ for build-heap — the sort-down phase is what makes the whole thing $O(n\log n)$.

False. "Complete" is only about shape (levels filled left-to-right). The heap property about values is a separate condition that must also hold.

False. Reversing the array scrambles the parent–child index relationships (2i+1, 2i+2 no longer point to the same conceptual nodes), so the result is generally neither a valid min-heap nor even a valid heap.

True. The front A[0..end-1] is the shrinking heap; the tail A[end..n-1] holds crowned maxima in final sorted position. One array, two zones — that's why it's in-place.

You must swap with the larger of the two children. Swapping with the left child even when the right is bigger can leave the right child larger than its new parent, violating the heap property.

You must go from the last internal node down to the root (n//2 - 1 down to 0). sift-down assumes both subtrees are already heaps, which is only true if you process children before parents — i.e. bottom-up.

Leaves (indices n//2 … n-1) have no children, so they're trivially heaps already. Sifting them is wasted work; we start at n//2 - 1, the last node that has a child.

It must be sift_down(A, 0, end). The just-crowned maximum sits at A[end] and is now sorted/frozen; passing n would drag it back into the heap and undo the work.

You must compare against both children (pick the larger) before deciding. Stopping early can leave the other, larger child above its parent — heap property broken.

For 0-indexing the parent is $\lfloor (i-1)/2\rfloor$. Plain i/2 is the 1-indexed formula; using it here mislinks nodes and corrupts the heap.

Because before the swap the whole region was already a valid heap; the swap only disturbs one node — the new root. Its two subtrees are still valid, so a single sift_down from the root restores everything in $O(\log n)$.

The back is where the final sorted position of the current maximum belongs (largest goes last). Placing it there lets us shrink the heap by one and never touch that slot again — building the sorted zone from right to left for free.

A complete tree has no gaps when numbered level-by-level, so the indices pack tightly with no wasted slots. Any gap would break the doubling formula and force us to store pointers, killing the in-place property.

There's no pivot to get unlucky with. The tree height is fixed at $\lfloor {\log }_{2}n\rfloor$ regardless of input order, so each of the $n$ sift-downs is bounded by $\log n$ every time — no input can trigger degeneracy.

The larger child becomes the new parent, so it must dominate its sibling too. Promoting the smaller child could leave the larger one below it, immediately re-violating the heap property.

Stability needs equal keys to keep relative order, but the crown-to-back swap moves an element across the whole array, leaping over equal keys. Those long-range jumps scramble the original ordering of ties.

In build-heap most nodes are near the bottom with short subtrees, so their sift-downs are cheap and the sum telescopes to $O(n)$. In sort-down every re-heapify starts at the root — full height $\log n$ each time — giving $O(n\log n)$.

Nothing — both loops (for i = n//2-1 … 0 and for end = n-1 … 1) don't execute. An empty array is already sorted, correctly handled by doing zero work.

Also a no-op: n//2 - 1 = -1 so build-heap skips, and the sort loop runs end from 0 down to 1 (empty range). One element is trivially sorted.

The heap property (parent ≥ child) holds everywhere with equality, so sift-down never swaps meaningfully; the array stays as-is and is (trivially) sorted. It runs in full $O(n\log n)$ but does minimal real work — and instability is invisible since keys are indistinguishable.

No — it's still $O(n\log n)$. An ascending array is not a max-heap (the max is at the end, not the root), so build-heap and every sift-down do full work. Heap sort has no "already-sorted" shortcut.

Height is $0$ (just a root). n//2 - 1 = -1, so build-heap performs zero sift-downs — nothing to sink.

Yes. The check r < n fails for the missing right child, so only the left child is considered. The bounds test handles the incomplete last level automatically — no special case needed.

No — sift-down only pushes values toward the leaves. Building and re-heapifying are designed so the only out-of-place node can always be fixed by sinking it; upward movement (sift-up) belongs to heap insertion, not to heap sort.