Heapsort, operation costs and choices

After this page, you should be able to:

• Separate priority-queue extraction from in-place heapsort.

• Compare repair, allocation, stability and output costs under stated assumptions.

Builds on: Heap construction, record priorities and sorting properties.

Code languages: Python defines the explanations, figures and self-checks. Use the language guide for native conventions and dependencies. Complete runnable topic examples: Python · JavaScript · Julia.

The Julia heap array starts at 1: parent=floor(i/2), children=2i and 2i+1. The support MinHeap implements heap repair rather than sorting on each removal. Stable record heaps compare priority and a unique counter before the payload; max queues negate numeric priorities.

Sorting and queue contracts are different¶

heapsort(a) rearranges a supplied list into ascending order, preserves every record/multiplicity and returns None. Empty and singleton lists are valid. Repeated min extraction instead consumes a heap and returns its removed values one by one; collecting them creates a separate ordered result. The record queue returns payloads under its tie policy, not necessarily bare priorities.

Repeated minima produce ordered output¶

For a fixed batch, build a min-heap and repeatedly remove its root. Each removal returns the smallest remaining value, so the emitted sequence is ascending. Construction costs $\Theta(n)$; n removals take $O(n\log(n+1))$ total time. Saving the emitted values creates an additional output collection.

That process differs in space usage from the in-place heapsort below, although both use heap order to organise sorting.

A max-heap places the next largest item at the end¶

To sort an existing array in ascending order, build a max-heap. Swap its root with the last item in the active prefix, shorten the prefix, and sift down within that prefix. The completed suffix is sorted and is no longer part of the active heap.

def heapsort(a):
    def sift_down_max(i, end):
        while 2 * i + 1 < end:
            child = 2 * i + 1
            right = child + 1
            if right < end and a[right] > a[child]:
                child = right
            if a[i] >= a[child]:
                break
            a[i], a[child] = a[child], a[i]
            i = child

    for i in range(len(a) // 2 - 1, -1, -1):
        sift_down_max(i, len(a))
    for end in range(len(a) - 1, 0, -1):
        a[0], a[end] = a[end], a[0]
        sift_down_max(0, end)

function heapsort(a) {
    function sift_down_max(i, end) {
        while (2 * i + 1 < end) {
            let child = 2 * i + 1, right = child + 1;
            if (right < end && a[right] > a[child]) child = right;
            if (a[i] >= a[child]) break;
            [a[i], a[child]] = [a[child], a[i]]; i = child;
        }
    }
    for (let i = Math.floor(a.length / 2) - 1; i >= 0; i--) sift_down_max(i, a.length);
    for (let end = a.length - 1; end > 0; end--) {
        [a[0], a[end]] = [a[end], a[0]]; sift_down_max(0, end);
    }
}

function heapsort!(a)
    function sift_down_max(i, last)
        while 2i <= last
            child = 2i; right = child + 1
            right <= last && a[right] > a[child] && (child = right)
            a[i] >= a[child] && break
            a[i], a[child] = a[child], a[i]; i = child
        end
    end
    for i in div(length(a), 2):-1:1; sift_down_max(i, length(a)); end
    for last in length(a):-1:2
        a[1], a[last] = a[last], a[1]; sift_down_max(1, last - 1)
    end
    return nothing
end

end is exclusive in the helper. It prevents a repair from moving completed suffix values back into the heap. The function changes a and returns None; empty and singleton inputs require no sorting iterations.

State time, space and stability separately¶

This heapsort has $O(n\log(n+1))$ worst-case time and $O(1)$ auxiliary space: it uses iterative sifting and no growing temporary list or recursion stack. Its worst-case comparison growth is asymptotically optimal for comparison sorting. This is a worst-case statement; equal keys can allow early stops during individual sifts.

Ordinary heapsort is not stable. Equal-key records can cross during root–end swaps even if every local comparison treats ties consistently. For [2_A, 2_B, 1], the shown max-heap sort comparing numeric keys can produce [1, 2_B, 2_A]. A stable application priority queue uses additional arrival keys; the bare heapsort has no such guarantee.

Implementation choices and suitability¶

This heapsort uses an iterative max-heap over an exclusive active prefix, so it has no recursion stack or copied sublists. Root–end swaps establish the sorted suffix and can reorder equal-key records. A stable priority queue with arrival metadata is a different implementation; it does not make this bare heapsort stable.

Worst-case time is O(n log(n+2)). The early-stop sifts shown can make all-equal input Θ(n), consistent with the sorting comparison. This does not change the worst-case bound. Use the function to understand in-place comparison sorting; for everyday Python application sorting, prefer the built-in stable interface.

Separate heap repair from storage management¶

The min/max record adapters have the same path/allocation bounds. No arbitrary-key search path follows from heap order, and no stable tie guarantee follows from choosing a child consistently. Neither a membership scan nor arbitrary-item deletion is part of the supplied queue class interface.

These bounds assume constant-time comparisons and array access. The heap’s own array stores $O(n)$ references with geometric capacity management. That input storage is distinct from a sift operation’s constant auxiliary space.

Match the invariant to the workload¶

An AVL tree supports logarithmic arbitrary-key lookup and linear sorted inorder traversal. A binary heap exposes a minimum immediately but supplies much less information about other keys. A basic AVL minimum query follows left links in $O(\log(n+1))$ time unless an extra minimum reference is maintained.

For repeated extreme selection with interleaved arrivals, a heap is a natural fit. For changing ordered data requiring arbitrary lookup and ordered traversal, a balanced search tree offers a different set of strengths. For ordinary batch sorting, Python’s stable sorted and .sort are useful application interfaces; implementing heapsort explains another strategy and its space trade-off.

Check your understanding¶

Predict the returned result and remaining heap before opening the explanation.

1. Does building a heap make its array globally sorted?

2. Can an O(1) root peek provide O(1) lookup of an arbitrary key?

Return to the topic overview, compare sorting strategies, or continue to Topic 11: graphs and traversal.