3.4.12 · D5Trees
Question bank — Heap operations — insert O(log n), extract-max - min O(log n), decrease-key
Before we start, one shared vocabulary reminder so no symbol is unearned:
- heap property = "every parent is both children" (max-heap) or " both children" (min-heap). It is the ONLY rule the structure enforces.
- complete tree = every level full except possibly the last, which fills strictly left-to-right, so it maps onto a gap-free array .
- sift-up = a misfit node climbs toward the root along one path. sift-down = a misfit node sinks toward a leaf along one path.
- height = the length of the longest root-to-leaf path, which is why the "" appears everywhere.
True or false — justify
A max-heap is a fully sorted array
False — only each parent–child chain is ordered; siblings have no defined order, so many different valid heaps hold the same numbers.
The root of a max-heap is always the largest element
True — the heap property chains upward: every parent dominates its subtree, and the root dominates all of them.
The second-largest element of a max-heap must be a child of the root
True — anything larger than every non-root node must sit directly under the root, so the runner-up is one of the (at most two) root children.
The smallest element of a max-heap is always the last array element
False — the minimum is some leaf, but not necessarily the last-filled one; leaves are unordered among themselves.
The smallest element of a max-heap is always in a leaf
True — if the minimum had a child, that child would be smaller, contradicting minimality; so it can have no children.
Every complete binary tree is a valid heap
False — "complete" is only the shape rule; a complete tree can still violate parent child everywhere.
Every valid heap is a complete binary tree
True — completeness is part of the heap definition; it is what lets us store the heap as a plain gap-free array.
In a min-heap, decrease-key can never increase the tree height
True — it only ever moves a node upward via sift-up; nodes never gain descendants, so no path lengthens.
insert followed by extract-max always returns the value you just inserted
False — it returns the current maximum, which is only the inserted value if that value is the new max.
A min-heap and a max-heap of the same array are just mirror images of each other
False — reversing the comparison changes which node bubbles where; the resulting structures are generally unrelated, not mirrored.
The array [9, 8, 7, 6, 5, 4] is a valid max-heap
True — checking each parent against children (9≥8,7; 8≥6,5; 7≥4) all hold, so the property is satisfied.
The array [1, 3, 2, 7, 4] is a valid min-heap
True — parent 1≤3,2 and parent 3≤7,4 both hold; the root being the minimum is consistent.
Spot the error
"To extract the max, promote the larger child of the root into the root."
Wrong — promoting a child leaves a hole in the middle, breaking completeness and array indexing. Move the last element to the root first, then sift-down.
"decrease-key on a min-heap should sift-down because the value got smaller."
Wrong — a smaller value belongs higher in a min-heap, so it must climb with sift-up; "decrease the value" is not "move down the tree."
"In a 0-indexed array, the parent of node is ."
Wrong — that is the 1-indexed rule. Zero-indexed uses ; for it gives 0, whereas wrongly gives 1.
"insert is because appending might reallocate the whole array."
Wrong — the sift-up cost is along one path; amortized array growth is , so insert stays .
"After extract-max, we only need to compare the new root with one child."
Wrong — sift-down must compare with both children to pick the larger, else you could swap into a slot that still violates the property.
"sift-up on a node checks both of its children each step."
Wrong — sift-up only ever compares the node with its single parent; children are irrelevant when climbing.
"Building a heap by inserting elements one-by-one is ."
Wrong — that is ; the special build uses sift-down from index down to 0, not repeated inserts.
"Heapsort is unstable, so a heap can't be used for a priority queue."
Wrong — instability of Heapsort is unrelated; a Priority Queue only needs fast peek/insert/extract, which the heap provides.
Why questions
Why is peek but extract ?
Peek just reads ; extract must move the last element up and then rebalance one full root-to-leaf path of length .
Why do we move the LAST element (not the largest child) into the root during extract?
The last element removal is the only way to keep the tree complete; any interior removal would leave a gap and destroy the array mapping.
Why does sift-up terminate in at most swaps?
Each swap moves the node one level toward the root, and there are only height-many levels, so it can climb at most that many times.
Why does a heap NOT sort the whole array despite always having the max on top?
The property only orders each parent above its own children; it says nothing about left-vs-right siblings, so ordering is partial, not total.
Why does Dijkstra's Algorithm specifically need decrease-key rather than plain insert?
When a shorter path to an already-queued vertex is found, its priority must drop in place; decrease-key updates that node in instead of leaving a stale duplicate.
Why is the array representation possible only for complete trees?
Completeness guarantees no gaps between indices and ; a tree with holes would need pointers or wasted slots to encode the missing positions.
Why does increase-key on a max-heap use sift-up while decrease-key on a max-heap would use sift-down?
A bigger value may now exceed its parent (climb up); a smaller value may now fall below a child (sink down) — the violation direction picks the primitive.
Why can Build-Heap (Heapify) achieve when it does sift-downs?
Most nodes are near the leaves where sift-down is cheap; summing per-level work with each level halving the node count gives a converging total that is , not .
Edge cases
What does sift-down do at a node with no children?
Nothing — with both child indices out of range there is no violation possible, so it stops immediately.
What happens if you extract-max from a heap of size 1?
You return the root, set size to 0, and skip sift-down entirely; the "move last to root" step trivially moves the element onto itself.
What does decrease-key(i, newVal) do when newVal equals the current value?
Nothing changes — the sift-up loop's condition () can only fire on a strict drop, so it exits at once.
Is it legal to call decrease-key with a value LARGER than the current key on a min-heap?
No — the operation's contract is that you only lower the key; raising it would demand sift-down and violate the intended upward-only design.
What is the parent of the root (index 0), and does it break the formula?
The root has no parent; is out of range, so sift-up's guard stops before ever computing it.
For a node with only a LEFT child (last parent in an odd-sized heap), how does sift-down behave?
It compares with the single existing child only; the missing right child index is out of range and simply skipped, so no phantom comparison occurs.
If all keys in a max-heap are equal, how many swaps does an insert of another equal key make?
Zero — sift-up needs a strict "greater than parent" to swap, so an equal new key stays put at the append position.
What is the height of a heap with exactly one node, and how many swaps can any operation make?
Height 0 — there is only the root, so both sift-up and sift-down have nowhere to go and perform zero swaps.
Recall One-line summary to lock it in
Every heap operation reduces to "which single path do I repair, and in which direction?" — sift-up for nodes that grew too extreme, sift-down for nodes that shrank too much, always along one root-to-leaf line of length .