Heapsort

Cost and properties

time	≤ 2n lg n compares
construction	≤ 2n compares — linear!
in place	yes
stable	no

Reference: Sedgewick & Wayne, §2.4; Floyd 1964.

Heapsort in Python

Runnable as-is, and written for reading. Watch the highlighted line move through it in the animation, or send it straight to the visualizer — it arrives with a test case ready to run, yours to edit.

Open in Visualizer

def heapsort(a):
    # 1-based helpers on a 0-based list: a[k-1] is heap position k.
    n = len(a)
    for k in range(n // 2, 0, -1):        # PHASE 1: build the heap
        _sink(a, k, n)                    #   bottom-up, right to left
    while n > 1:                          # PHASE 2: sortdown
        _swap(a, 1, n)                    #   max to its final position
        n -= 1                            #   shrink the heap
        _sink(a, 1, n)                    #   restore heap order
    return a

def _sink(a, k, n):
    while 2 * k <= n:
        j = 2 * k
        if j < n and a[j - 1] < a[j]:
            j += 1                        # the larger child
        if not a[k - 1] < a[j - 1]:
            break
        _swap(a, k, j)
        k = j

def _swap(a, i, j):
    a[i - 1], a[j - 1] = a[j - 1], a[i - 1]

Why it works

Two phases

Construction sinks every internal node, working right to left from n/2 — the leaves (the second half of the array) are already heaps of size one, so they are skipped. Afterwards the whole array is heap-ordered. Sortdown then repeatedly exchanges a[1] (the maximum) with the last heap position, shrinks the heap by one, and sinks the new root. The keys accumulate in ascending order at the right end.

Why construction is linear

Half the nodes are leaves and sink zero levels, a quarter sink at most one, an eighth at most two … The total is bounded by n·Σ(k/2^k) < 2n. Building a heap by n successive inserts instead would cost n lg n — the bottom-up direction is what makes it linear, and it is one of the most useful counter-intuitive results in the course.

The best guarantees, and still not the default

Heapsort is n log n in the worst case and in place — mergesort gives up the second, quicksort the first. Yet library sorts choose quicksort, because heapsort's inner loop jumps between k, 2k and 2k+1: long strides, poor cache locality, and more compares than quicksort. It is the right choice when worst-case time and constant space both matter — and it is the fallback that keeps introsort's guarantee.

Not stable

Long-range exchanges reorder equal keys. Also note phase 2 destroys the heap it just built: after sorting, the array is sorted, not heap-ordered.

What to try in the animation

Phase 1 is the surprise: heap construction is linear, not n log n, because most nodes are near the bottom and sink at most one or two levels.

The animation is generated from the input box, in your browser — press Animate after editing it. To execute the Python itself, use Open in Visualizer above.

• random — 7 10 5 3 8 4 2 9 6 1
• SORTEXAMPLE — S O R T E X A M P L E
• already sorted — 1 2 3 4 5 6 7 8 9 10
• reverse sorted — 10 9 8 7 6 5 4 3 2 1

Open Heapsort in the player →

The rest of Priority queues

• Binary heap (MaxPQ) A complete binary tree stored in an array, where no key exceeds its parent.