Algorithms and data structures · Intermediate

Heapsort: move the maximum into a sorted suffix

Trace heap construction and repeated extraction to explain linear heap building and logarithmic restoration costs.

Ask Logeia about this articleTry the three questionsReview your answers

Updated

On this page
  1. A heap is not a sorted array
  2. Extract from a four-element heap
  3. Why bottom-up building is linear
  4. Account for stability and storage
  5. Ask Logeia about this articleCheck your understanding

A heap is not a sorted array

Ascending heapsort begins with a max-heap. Each parent key is at least as large as its children, making the root a global maximum, but siblings and separate subtrees need not be ordered. With zero-based indices, children of i are at 2i+1 and 2i+2. Exchange the root with the last element of the active heap, reduce the active size, and restore the heap by moving the new root downward. This sift-down operation must exclude the suffix that has already been sorted.

Extract from a four-element heap

For [4,1,3,2], bottom-up adjustment can produce the max-heap [4,2,3,1]. Exchanging 4 with the final 1 and restoring the three-element heap gives [3,2,1,4]. Next exchange 3 with the end of the active range and restore that range to obtain [2,1,3,4]. Each extraction extends the sorted suffix one position to the left. No physical removal from the array is required. Maintaining a separate active length is enough to distinguish the heap from the final suffix and prevents accidentally moving a completed element.

Why bottom-up building is linear

Building a heap through successive insertions has an O(n log n) upper bound, but the standard bottom-up construction takes O(n). Most nodes are near the leaves and can move only a short distance; only a few nodes can travel many levels. Bounding the number of nodes of height h by roughly n/2^(h+1) makes the sum of all downward travel linear. The extraction stage then performs at most n restorations, each taking O(log n). Together these stages provide an O(n log n) worst-case running-time guarantee with constant-time comparisons.

Account for stability and storage

An iterative sift-down implementation uses O(1) auxiliary storage beyond the input array. A recursive implementation must also account for its call stack. Distant exchanges can change the original order of equal keys, so ordinary heapsort is not stable. Its nonsequential accesses may behave differently from the sequential scans used in merging, even when both algorithms have the same asymptotic time bound. Check empty and singleton heaps, a node with only one child, and duplicate keys. A comparison function must provide a consistent ordering throughout both construction and extraction.

Reading and practice are recorded separately in this browser, for each language.

Learn this in order

Build your CS foundations · STEP 10

Choose a learning path