Heap Sort Complete Guide

Algorithm • hard

Heap sort is two algorithms in one: build a max-heap from the array, then repeatedly extract the max and place it at the end of the unsorted region.

It guarantees **O(n log n) in the worst case** with **O(1) extra memory**. It's the only mainstream comparison sort with both properties.

It's not stable and has poor cache locality compared to merge sort or quicksort, which is why most language standard libraries don't choose it as the default.

Typical Complexity Baseline

Metric	Value
Time	`O(n log n)` (best/avg/worst)
Space	`O(1)`

See It

Concept Diagram

A small animated SVG that illustrates the core idea the moving parts you need to keep in your head when you read the rest of the guide.

Heap sort repeatedly extract the max

Build a max-heap, then move the root to the end and re-heapify the smaller heap.

Step 1/30Max-heap of 8 values. Each parent ≥ its children. Root = 9 (the max).

Speed

Watch First

Video Explainer

A quick visual walkthrough before the detailed sections pick the format that helps you learn fastest.

Heap sort in 4 minutes

Channel: Michael Sambol

Watch on YouTube →

Mechanics

Core Concepts

The building blocks and terminology you need before everything else clicks. Skim or deep-read.

Max-heap property

What it is Every parent is ≥ both children. The largest value is always at index 0.

Why it matters Max-heap property is a required building block for understanding how Heap Sort stays correct and performant on large inputs.

Array representation

What it is Heap lives in the array: parent of i is (i−1)/2, children are 2i+1 and 2i+2.

Why it matters Array representation is a required building block for understanding how Heap Sort stays correct and performant on large inputs.

Heapify (build)

What it is Bottom-up sift-down from the last non-leaf to index 0, O(n) total.

Why it matters Heapify (build) is a required building block for understanding how Heap Sort stays correct and performant on large inputs.

Sift down

What it is Push a value down to its correct level by swapping with the larger child.

Why it matters Sift down is a required building block for understanding how Heap Sort stays correct and performant on large inputs.

Extract max

What it is Swap root with last unsorted element, shrink heap, sift the new root down.

Why it matters Extract max is a required building block for understanding how Heap Sort stays correct and performant on large inputs.

Complete binary tree

What it is Every level filled except possibly the last, which fills left-to-right. This is what lets us store the heap in a flat array.

Why it matters Every level filled except possibly the last, which fills left-to-right. This is what lets us store the heap in a flat array. In Heap Sort, this definition helps you reason about correctness and complexity when inputs scale.

Heapify

What it is Convert an arbitrary array into a heap in O(n) time using bottom-up sift-down.

Why it matters Convert an arbitrary array into a heap in O(n) time using bottom-up sift-down. In Heap Sort, this definition helps you reason about correctness and complexity when inputs scale.

Sift down (bubble down)

What it is Restore heap property at a node by swapping with the larger child until the property holds.

Why it matters Restore heap property at a node by swapping with the larger child until the property holds. In Heap Sort, this definition helps you reason about correctness and complexity when inputs scale.

In-place

What it is Uses O(1) extra memory the heap and the sorted output share the array.

Why it matters Uses O(1) extra memory the heap and the sorted output share the array. In Heap Sort, this definition helps you reason about correctness and complexity when inputs scale.

Unstable

What it is Sift-down can swap a value past an equal value, breaking original input order.

Why it matters Sift-down can swap a value past an equal value, breaking original input order. In Heap Sort, this definition helps you reason about correctness and complexity when inputs scale.

Walkthrough

Putting It All Together

Every frame of the concept diagram, laid out top-to-bottom so you can scroll through the algorithm at your own pace.

Step 1/30

Max-heap of 8 values. Each parent ≥ its children. Root = 9 (the max).

Step 2/30

Extract 9: swap root with last leaf (2).

Step 3/30

Shrink heap 9 is locked. Sift down 2: max of children (7, 8) is 8.

Step 4/30

2 < 8 → swap. 2 moves to index 2.

Step 5/30

Continue sift: max of children (3, 4) is 4.

Step 6/30

2 < 4 → swap. No more children → sift complete.

Step 7/30

Extract 8: swap root with last (2).

Step 8/30

Sift 2: max of (7, 4) is 7.

Step 9/30

Swap 2 ↔ 7.

Step 10/30

Continue: max of (5, 6) is 6.

Step 11/30

Swap 2 ↔ 6. No more children → done.

Step 12/30

Extract 7: swap root with last (3).

Step 13/30

Sift 3: max of (6, 4) is 6.

Step 14/30

Swap 3 ↔ 6.

Step 15/30

Continue: max of (5, 2) is 5.

Step 16/30

Swap 3 ↔ 5. Done.

Step 17/30

Extract 6: swap root with last (2).

Step 18/30

Sift 2: max of (5, 4) is 5.

Step 19/30

Swap 2 ↔ 5.

Step 20/30

Continue: only one child (3). 2 < 3 → swap.

Step 21/30

Done.

Step 22/30

Extract 5: swap root with last (2).

Step 23/30

Sift 2: max of (3, 4) is 4.

Step 24/30

Swap 2 ↔ 4. No more children → done.

Step 25/30

Extract 4: swap root with last (2).

Step 26/30

Sift 2: child is 3. 2 < 3 → swap.

Step 27/30

Done.

Step 28/30

Extract 3: swap root with last (2).

Step 29/30

Heap is just [2] already valid.

Step 30/30

Last element drops to the tail. Done n log n total work.

Tradeoffs

How It Compares

When this technique wins, when it loses, and what to reach for instead.

vs. Quick Sort

Choose this when Choose heap sort when you cannot tolerate quicksort's O(n²) worst case (adversarial input, hard real-time deadlines).

Tradeoff Quick sort is typically 2–3× faster in practice due to cache locality and lower constant factors.

vs. Merge Sort

Choose this when Choose heap sort when you need O(1) extra space merge sort needs O(n).

Tradeoff Merge sort is stable and friendlier to the cache; heap sort jumps around the array.

vs. Priority Queue (heap-based)

Choose this when Use heap sort when you need a fully sorted result; use a priority queue when you only need partial extraction (top-k, streaming).

Tradeoff PQ is the right structure for incremental insert/extract; heap sort is for one-shot sorting.

In Production

Real-World Stories

Where this shows up at real companies and what the on-call engineer learned the hard way.

Linux kernel

The kernel uses heap sort (sort.c) for a worst-case-bounded in-place sort because dynamic allocation is risky in kernel context and quicksort's O(n²) is unacceptable.

Takeaway When you can't allocate and can't gamble on average-case, heap sort is the safe default.

Real-time audio/video pipelines

Frame schedulers that must hit a 16.6ms deadline at 60fps prefer heap sort or heap-based PQs over quicksort because the latency upper bound is what determines whether a frame drops.

Takeaway Predictable worst-case beats faster average-case under hard deadlines.

Top-K analytics

Systems that find top-K trending items, hottest queries, or k-largest values stream data through a min-heap of size K a direct application of heap sort's mechanics.

Takeaway The heap data structure shows up far more often than heap sort itself.

Code

Implementation

A clean reference implementation in TypeScript, Python, and Go. Switch languages with the toggle.

First build a max-heap in O(n) via bottom-up sift-down. Then repeatedly swap root to end and sift down the new root.

Complexity: Time O(n log n), Space O(1), Unstable

In-place heap sort with bottom-up heapify

Language

function heapSort(values: number[]): number[] {
  const sortedValues = [...values]
  const arrayLength = sortedValues.length

  function siftDown(rootIndex: number, heapEnd: number): void {
    let currentIndex = rootIndex
    while (true) {
      const leftChildIndex = 2 * currentIndex + 1
      const rightChildIndex = 2 * currentIndex + 2
      let largestIndex = currentIndex
      if (leftChildIndex < heapEnd && sortedValues[leftChildIndex] > sortedValues[largestIndex]) largestIndex = leftChildIndex
      if (rightChildIndex < heapEnd && sortedValues[rightChildIndex] > sortedValues[largestIndex]) largestIndex = rightChildIndex
      if (largestIndex === currentIndex) return
      ;[sortedValues[currentIndex], sortedValues[largestIndex]] = [sortedValues[largestIndex], sortedValues[currentIndex]]
      currentIndex = largestIndex
    }
  }

  // Build heap (O(n) bottom-up)
  for (let heapifyRoot = Math.floor(arrayLength / 2) - 1; heapifyRoot >= 0; heapifyRoot -= 1) {
    siftDown(heapifyRoot, arrayLength)
  }
  // Extract max repeatedly
  for (let heapEnd = arrayLength - 1; heapEnd > 0; heapEnd -= 1) {
    ;[sortedValues[0], sortedValues[heapEnd]] = [sortedValues[heapEnd], sortedValues[0]]
    siftDown(0, heapEnd)
  }
  return sortedValues
}

Watch Out

Common Problems and Failure Modes

The bugs and edge cases that bite engineers most often. Skim before you ship.

Heapifying top-down (O(n log n)) instead of bottom-up (O(n)) most people get this wrong on the first pass.
Off-by-one in child index: children of i are 2i+1 and 2i+2, not 2i and 2i+1 (that's for 1-indexed heaps).
Forgetting to shrink the heap region after each extract sift-down must respect the current heap size, not the array length.
Building a min-heap when you need ascending sort, then extracting wrong end of array.
Assuming heap sort is stable it isn't. If you need stability, use merge sort or wrap each value with its index.

Pro Tips

Tips and Tricks

Small habits that pay off every time you reach for this pattern.

Start by writing the core invariant in one sentence before coding.
Test empty, single-item, and duplicate-heavy inputs early.
Pick the pattern first (map, pointers, recursion, heap, etc.), then implement details.
Track both time and space complexity while iterating on correctness.

Pattern Recognition

When to Use

Concrete signals that tell you this is the right pattern both at work and on LeetCode.

Real-system usage signals

When you need a worst-case O(n log n) guarantee without quicksort's O(n²) corner cases.
When memory is tight heap sort is in-place, unlike merge sort.
As the foundation for priority queues every heappush/heappop is essentially heap sort's inner mechanic.
Embedded/real-time systems where predictable upper-bound runtime matters more than average-case speed.

LeetCode-specific tips (pattern-identification signals)

Identification signal: focus on verbs like optimize, order, schedule, traverse, or shortest path; these often indicate algorithm-first problems.
Identification signal: if brute force is easy to write but constraints are large, you likely need a known algorithmic pattern.
Map the prompt to pattern families first (search, traversal, greedy, DP, graph) before coding details.
For Heap Sort questions, start by naming the core invariant before writing code.
Use the constraint section to set time/space target first, then pick the data structure/algorithm.
Solve one tiny example by hand and map each transition to your variables before implementing.
Run adversarial cases: empty input, duplicates, max-size input, and sorted/reverse patterns when relevant.
During interviews, explain why your approach is the right pattern for this prompt, not just why the code works.

Practice

LeetCode Progression

A curated easy-to-hard problem ladder. Each one reinforces a specific aspect of the pattern.

#	Problem	Difficulty	Typical Complexity
1	Kth Largest Element in an Array	Medium	`O(n log k)` heap, `O(n)` QuickSelect
2	Top K Frequent Elements	Medium	`O(n log k)`
3	K Closest Points to Origin	Medium	`O(n log k)`
4	Sort an Array	Medium	`O(n log n)` with heap sort
5	Find Median from Data Stream	Hard	`O(log n)` per insert
6	Merge k Sorted Lists	Hard	`O(n log k)`
7	Sliding Window Maximum	Hard	`O(n)` deque, `O(n log k)` heap