Heapsort¶

A comparison sort that builds a heap and repeatedly extracts its extremal element to produce an ordered sequence.

Version: v1 · 2026-09-28 · History
Domain-specific #: 9815
Domain group: Applied Sciences & Engineering
Origin domain: Computer Science & Software Engineering
Subdomain: Comparison Sorting Algorithms → Computer Science & Software Engineering
Aliases: Heap sort

Core Idea¶

Heapsort orders a finite input by maintaining a heap over the not-yet-emitted elements. In a max-heap, the largest remaining element is at the root; the usual array form swaps that root into the final free slot, shrinks the heap, and restores the invariant. Repeating those actions grows a sorted suffix until every element is placed. A min-heap can instead pop successive smallest elements into a separate output list. Both enact the same heap-selection sorting relation, but they differ in storage layout.

For the standard binary-heap method, the worst-case number of operations grows as O(n log n). The familiar O(1) auxiliary-space result applies to the array in-place version; it should not be assigned to Python's documented push/pop example, which allocates heap and result lists. Equal-key order is not generally preserved, so the usual algorithm is unstable. Heapsort may be used as a fallback when another sort threatens poor worst-case behavior, but that surrounding introspective algorithm is not part of heapsort's own identity.

Structural Signature¶

Sig role-phrases:

Sortable input and order — Provides finite elements and a comparison/key order to satisfy in the output. It is constitutive. Counterfactual: A heap used only as a priority queue without full ordering is not heapsort.
Heap invariant — Keeps an extremal value at a root relative to the remaining elements. It is constitutive. Counterfactual: Removing the heap structure leaves another selection-sort strategy.
Repeated root extraction — Emits the extremal value and reduces the unsorted heap on each iteration. It is constitutive. Counterfactual: Building a heap but never exhausting it does not sort the collection.
Invariant restoration — Reheapifies after each removal so the next root remains extremal. It is constitutive. Counterfactual: Without restoration later roots may be out of order.
Output and storage variant — Distinguishes in-place max-heap suffix construction from a separate-output min-heap implementation. It is boundary. Counterfactual: The identity survives variant changes, but O(1) auxiliary-space claims do not.

What It Is Not¶

Not heap construction alone. A heap must be repeatedly drained to form the ordered result.
Not any priority queue. Isolated next-item requests do not amount to sorting an entire finite input.
Not necessarily in place. Min-heap push/pop examples can allocate another heap and output.
Not a stable sort by default. Equal keys can change relative order.
Closest near-miss. Priority-queue extraction is the closest miss: it may use the same heap operation, but if the operation serves individual requests rather than producing a fully ordered sequence it is not the sorting algorithm.

Scope of Application¶

Array sorting. Use the shrinking max-heap suffix method for bounded extra storage.
Library pedagogy. Compare Python's min-heap demonstration with the in-place array variant.
Complexity analysis. Separate worst-case time, auxiliary memory, and stability.
Hybrid sorts. Recognize heap fallback as a use rather than a defining phase.

Clarity¶

The algorithm must both establish a heap and repeatedly remove its root while repairing the remaining heap until all values are ordered. A priority queue with only one pop is the nearest miss. A max-heap can write a sorted suffix in place; Python's documented min-heap version writes a separate result. Both are heapsort, but only the former supports the usual constant auxiliary-storage description.

Manages Complexity¶

The heap invariant turns each next-extreme choice into a logarithmic repair rather than a full scan. This yields a worst-case O(n log n) comparison bound while hiding practical costs of heap accesses and key comparison. Time, memory, and stability remain separate coordinates: the implementation form, not the name alone, settles the last two.

Abstract Reasoning¶

Specify the input and comparison/key order.
Construct or populate a heap with its extremal element at the root.
Extract the root into the ordered output or array suffix.
Repair the heap invariant over the remaining elements.
Repeat to exhaustion and state the variant's storage and stability limits.

Knowledge Transfer¶

The heap-build/extract/repair strategy carries from the in-place array algorithm to Python's separate-output min-heap version because the extremal invariant and full ordered emission remain intact. The O(1) auxiliary-space claim does not transfer to the latter. A scheduler can use the same heap operations but is only analogous unless it consumes the collection as a complete sorting problem.

Examples¶

Canonical¶

For input [4,1,3,2], establish a max-heap, place its current largest root at the end of the array, repair the smaller heap, and repeat until the suffix contains the sequence [1,2,3,4]. The key is the maintained extremal-root condition through every shrinking step; merely swapping the first element with the final slot once would not sort the array.

Mapped back: Sortable input and order → four integers in ascending order; Heap invariant → max element at heap root; Repeated root extraction → largest element sent to the growing sorted suffix; Invariant restoration → heap repaired after each exchange; Output and storage variant → usual in-place max-heap suffix form.

Applied / In Practice¶

Python's official heapq documentation publishes a heapsort function that pushes every input item to a min-heap and then pops the heap until a separate sorted list is complete. The documentation notes that this implementation is not stable. It is an attested heapsort variant, but unlike the array-suffix max-heap form it allocates a distinct heap/output structure and does not justify an O(1) auxiliary-space claim.

Mapped back: Sortable input and order → the documented iterable and Python item comparison; Heap invariant → min-heap maintained by heapq; Repeated root extraction → heappop called until heap empty; Invariant restoration → heapq pop maintains its heap condition; Output and storage variant → separate result list rather than in-place suffix.

Structural Tensions¶

T1 — Worst-Case Bound versus Practical Locality. O(n log n) comparison time does not imply every heap arrangement is faster than a tuned quicksort on real hardware.

Diagnostic: Which performance axis is being compared?

T2 — In-Place Form versus General Heap Strategy. The common array algorithm uses constant auxiliary storage, while a push/pop demonstration uses a separate heap and output.

Diagnostic: Which variant supports the memory claim?

Structural–Framed Character¶

Heapsort is structural-leaning within the domain-specific spectrum. Its evaluative weight is limited: runtime, memory, and stability are performance properties rather than a claim that the algorithm is universally best. It is a designed human procedure, but the relation between heap invariant and ordered extraction can be proved without any particular institution or programming language. Its historical invention is not constitutive of a run of heapsort. Vocabulary such as heap root, compare, reheapify, and sorted suffix is computational; the same word “heap” in another setting does not transfer the algorithm. A scheduler may reuse heap operations, yet it is not recognized as heapsort unless it orders a complete finite input.

The portable skeleton is a well-defined finite input-to-output procedure, carried by prime Algorithm; the nearer sorting genus fixes the ordered-permutation goal. The named algorithm narrows that skeleton through heap-based extremal selection. Its character: formally structural but still anchored to comparison sorting and heap semantics, not a free-standing prime of all extremal processes.

Structural Core vs. Domain Accent¶

Heapsort shares a general procedural skeleton with many algorithms, but its sorting identity is narrower.

What is skeletal. A finite input, an ordering objective, invariant-preserving steps, and a terminating output form the portable algorithmic relation. Separately, maintaining an extremal element for repeated selection is a reusable data-structure strategy. Prime Algorithm owns the broad procedural pattern; the Sorting Algorithm genus adds full ordered rearrangement. A priority queue can exploit the selection tactic without inheriting the sort's complete-output objective.

What is domain-bound. Heapsort requires comparisons or an orderable key, a heap relation among remaining items, extremal-root extraction, and repair until the finite input is exhausted. Those conditions explain its O(n log n) worst-case bound. The in-place max-heap and Python's separate-output min-heap realize the same identity with different memory layouts. Remove repeated repair or stop after only occasional queue requests and the procedure is no longer this sort.

Why this does not clear the prime bar. The algorithmic sequence can be recognized in innumerable substrates, but “heapsort” does not name all staged selection, prioritization, or invariant restoration. Its defining data structure and sorted-permutation endpoint are computational specializations. A social process choosing the current highest-priority item may be compared to a heap, but without an actual comparison ordering and heap-maintained full sorting task it is analogy. The cross-domain reach belongs to Algorithm, not to a relabeled heapsort.

This entry is a kind of Sorting Algorithm.

Parent — sorting algorithm. Heapsort is a finite input-to-ordered-permutation procedure, narrowed by heap maintenance and extremal extraction.
Related — priority queue. It supplies heap operations but does not by itself require full ordered emission.

Relationships to Other Abstractions¶

Current abstraction Heapsort Domain-specific

Parents (1) — more general patterns this builds on

Heapsort is a kind of Sorting Algorithm Domain-specific

Heapsort rearranges finite comparable input into order by maintaining and draining a heap.

Hierarchy paths (2) — routes to 2 parentless roots

Heapsort → Sorting Algorithm → Algorithm → Function (Mapping)

Show alternative path (1)

Neighborhood in Abstraction Space¶

Heapsort sits in a sparse region of the domain-specific corpus (63^rd percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Memory Storage, Retrieval & Encoding (9 abstractions)

Nearest neighbors

X + Y Sorting — 0.85
Online Codes — 0.85
Time-sharing — 0.85
Kostka number — 0.84
Optimizing Compiler — 0.84

Computed from structural-signature embeddings · 2026-10-08

Not to Be Confused With¶

Heapify. Tell: Was a heap merely established, or was it repeatedly drained into order?
Selection sort. Tell: Is an extremal heap invariant maintained after removals?
Introsort. Tell: Is heapsort the whole procedure or a fallback phase of another algorithm?
Stable sorting. Tell: Must equal keys retain their original relative order?

References¶

Python Software Foundation, heapq module documentation, heapsort example: https://docs.python.org/3.10/library/heapq.html
Frozen Wikipedia discovery revision: https://en.wikipedia.org/wiki/Heapsort (revision 1369261292).
Preserved source candidate: https://www.math.cmu.edu/~af1p/Texfiles/Best.pdf
Preserved source candidate: https://www.cs.princeton.edu/research/techreps/TR-293-90
Preserved source candidate: https://inference.org.uk/mackay/sorting/sorting.html
Preserved source candidate: http://staff.gutech.edu.om/~rudolf/Paper/buh_algorithmica94.pdf
Preserved source candidate: https://web.archive.org/web/20180614144211/http://staff.gutech.edu.om/~rudolf/Paper/buh_algorithmica94.pdf
Preserved source candidate: http://pubman.mpdl.mpg.de/pubman/item/escidoc:1834997:3/component/escidoc:2463941/MPI-I-94-104.pdf
Preserved source candidate: https://core.ac.uk/download/pdf/82350265.pdf
Preserved source candidate: http://people.mpi-inf.mpg.de/~mehlhorn/Toolbox.html