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.