How it works
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.
Compare heap sort with merge sort on space: both are n log n, but only heap sort needs no auxiliary array.
Common error
Assuming repeated insertion and bottom-up building cost the same. They do not.
Worked example
Example
Bottom-up build: sift down from last internal node
Most nodes are near the leaves
Build-heap total: O(n)
Repeated extraction in heap sort: O(n log n)Bottom-up construction is linear because the total downward work is weighted toward the many shallow subtrees. Standard in-place array heap sort uses a max-heap to place each next maximum at the shrinking array end.
Exercises
7.4.1 · Explain
Compare building a heap by n separate insertions with bottom-up build in worst-case time.
Show solution
Repeated insertion has an O(n log n) worst-case bound. Bottom-up build is O(n).
7.4.2 · Explain
What are the standard in-place heap sort time and auxiliary-space bounds?
Show solution
It runs in O(n log n) time and uses O(1) auxiliary space with iterative sift operations. It is generally not stable.