Unit 7 · Moderate
A tree with a weaker ordering than a BST, which is exactly what makes it cheap to maintain. The heap property constrains parents against their own children only, so the extreme value sits at the root and nothing else is sorted.
What a strong answer looks like
A strong Unit 7 answer distinguishes the heap property from full sorting and explains why the weaker guarantee is sufficient for the task.
Know
Every parent compares correctly against its own children. Siblings are unordered and the structure is not sorted, which is why maintaining it is cheap.
Apply
Use a heap when only the extreme element is needed repeatedly.
Watch out
Expecting sorted order from a heap traversal. Only the root is guaranteed.
Study move
Draw a valid min-heap whose level order is clearly unsorted.
Know
A complete binary tree stores in an array with no gaps, so parent and child indices are computed arithmetically rather than stored.
Apply
Use index arithmetic to move between parent and children without references.
Watch out
Applying the arithmetic to a tree that is not complete, where the mapping breaks.
Study move
Given an array-backed heap, name the children of a specific index.
Know
Insertion appends and sifts up; extraction takes the root, moves the last element there, and sifts down. Both cost the height of the tree.
Apply
Trace a sift by comparing only against the relevant child at each level.
Watch out
Sifting down against the wrong child, which breaks the property one level below.
Study move
Extract the minimum from a drawn heap and record every swap.
Know
Bottom-up construction costs linear time because most nodes sift only a short distance. Heap sort then extracts n times, giving n log n in place.
Apply
Compare heap sort with merge sort on space: both are n log n, but only heap sort needs no auxiliary array.
Watch out
Assuming repeated insertion and bottom-up building cost the same. They do not.
Study move
Explain why bottom-up building is linear despite each sift costing up to log n.
Connections and techniques that receive extra attention in this unit.
Related topics some schools attach to this unit and others leave out. Covered on request rather than assumed.
Modeling drill
Given a stream of values from which only the largest few are ever needed, design a heap-based approach and state its cost per value.
