Heap Sort — In-Place Priority Queues as a Sort

Heap sort turns a max-heap into an in-place sorting engine: repeatedly extract the largest element to the end and shrink the heap. It guarantees O(n log n) worst case without the extra array merge sort needs.

Why this shows up in the real world

Embedded flight systems sometimes forbid large auxiliary buffers—heap sort’s in-place nature helps. Database engines occasionally externalize merge phases but use heaps for bounded-memory top‑K queries that share machinery with heap sort. Anywhere you already maintain a priority queue for scheduling, understanding heap sort links “priority” to “sorted output.”

Core idea (explained for students)

Build a max-heap in O(n) with bottom-up heapify. Swap root a[0] with a[n-1], reduce heap size by 1, and sink the new root. Repeat. The tail of the array becomes sorted from the right. Unlike quicksort’s worst case, heap sort’s height is always logarithmic, but cache behavior is often worse than quicksort on random arrays—constants matter in practice.

Try this in Python

import heapq


def heapsort(iterable):
    h = []
    for value in iterable:
        heapq.heappush(h, value)
    return [heapq.heappop(h) for _ in range(len(h))]


print(heapsort([3, 1, 4, 1, 5]))

Common mistakes

• Off-by-one heap size when sinking children.
• Mixing min-heap logic with max-heap indexing.
• Forgetting heap sort is not stable in typical textbook variants.

Key takeaways

• O(n log n) time, O(1) extra space for classic in-place variant.
• Worse constant factors than tuned quicksort but predictable worst case.
• Great bridge between priority queues and sorting theory.