Vibe Engines Learn
ALGORITHMS · 10  /  HEAP SORT

The Tournament.

Twelve numbers, no order. Run a tournament where every parent must beat its children, crown the champion at the top — then pluck it off, again and again, until the whole array falls into place. O(n log n), with no extra memory.

THE GIST · 20 SECONDS

Heap sort reads an array as a binary tree — node i's children are 2i+1 and 2i+2. Phase 1: build a max-heap so every parent outranks its kids and the biggest value sits at the root. Phase 2: swap that root maximum to the end, shrink the heap, and sift the new root down to fix it — repeat. Each sift is O(log n), done n times: O(n log n), entirely in place.

  • Max-heapevery parent ≥ its children
  • Rootindex 0 — the current max
  • Sift-downsink a node past bigger kids
  • In placeO(1) extra memory

Hit Step to make the next move — or Play and watch the heap build, then drain into sorted order.

UNDER THE HOOD

What you just played, written down

An array is a binary tree if you agree on the index math. Build it into a max-heap, then repeatedly harvest the root. Two phases, one array, no extra memory.

How heap sort thinks — four moves

  1. The array is a tree. Node i's children live at 2i+1 and 2i+2; its parent at (i−1)/2. No pointers — just arithmetic.
  2. Build a max-heap. Sift-down every internal node from the last parent up to the root. Now every parent beats its children, so the max sits at index 0.
  3. Harvest the root. Swap index 0 with the last unsorted slot — the biggest value is now in its final place. Shrink the heap by one.
  4. Restore & repeat. Sift the new root down to fix the heap, then harvest again. After n rounds the array is sorted.
WHY THE ARRAY GROWS SORTED FROM THE RIGHT

Each harvested maximum lands at the current end of the heap and is locked. So the sorted region builds up from the right edge inward, largest first — while the heap shrinks on the left.

The whole thing in code

def heap_sort(a):
    n = len(a)
    # PHASE 1 - build a max-heap, bottom-up
    for i in range(n // 2 - 1, -1, -1):
        sift_down(a, i, n)
    # PHASE 2 - harvest the root, shrink, restore
    for end in range(n - 1, 0, -1):
        a[0], a[end] = a[end], a[0]   # max to the end
        sift_down(a, 0, end)          # fix the heap

def sift_down(a, root, end):
    while 2*root + 1 < end:
        child = 2*root + 1
        if child + 1 < end and a[child+1] > a[child]:
            child += 1                # bigger child
        if a[root] >= a[child]:
            break                     # heap ok here
        a[root], a[child] = a[child], a[root]
        root = child
TIMEO(n log n)best = avg = worst
SPACEO(1)in place, no buffer
BUILDING THE HEAP IS ONLY O(n)

Sifting down looks like n·log n, but most nodes are near the bottom with almost no height to fall. The heights sum to a geometric series, so build-heap is O(n) — the log n only shows up in the harvest phase.

⚠ Not stable, poor cache locality

Equal keys can be reordered, so heap sort is not stable. And it hops all over the array following child indices, so it's less cache-friendly than quicksort — often losing in raw speed despite the same big-O.

↔ Sift-down vs sift-up

Building a heap by sift-down from the bottom is O(n); building it by inserting one-at-a-time with sift-up is O(n log n). Same heap, different cost — bottom-up wins.

★ Where heaps shine

The heap itself powers priority queues: Dijkstra, A*, event simulation, top-k / streaming medians, and Huffman coding. Heap sort is the heap used once, to sort.

SOLVE IT YOURSELF

Solve it: heap sort in place

This one is yours to write — in Python or TypeScript, running for real in your browser. Build a max-heap, then harvest the root n times. Edit the stub, hit Run (or ⌘/Ctrl + Enter), and watch the hidden tests. Stuck? the hints are below and Reveal solution is one click away.

YOUR TASK

Implement heap_sort(nums): return the list sorted ascending. Use a binary max-heap — build it with sift-down, then repeatedly swap the root maximum to the end and sift down to restore. Aim for O(n log n) time and in-place O(1) extra space.

HINTS — 4 IDEAS
  1. Children of i are 2*i+1 and 2*i+2; a node with a child at 2*i+1 < end is internal.
  2. sift_down(root, end): pick the larger child, swap if it beats the root, then continue from the child.
  3. Build the heap by sifting down from n//2 - 1 back to 0.
  4. Harvest: for end from n-1 down to 1, swap a[0] with a[end], then sift_down(0, end).
CPython · WebAssembly
QUICK CHECK

Did it stick?

FAQ

Heap sort, answered

What is heap sort?

A comparison sort that builds the array into a max-heap (every parent ≥ its children, so the max is at index 0), then repeatedly swaps that root maximum to the end, shrinks the heap, and sifts down to restore it. It runs in O(n log n) using O(1) extra space.

What is a binary heap?

A complete binary tree packed into an array. For index i, children are at 2i+1 and 2i+2, parent at (i−1)/2. In a max-heap every parent is at least as large as its children — no pointers needed, the indices encode the tree.

What is sift-down (heapify)?

Restoring the heap at a node that may be too small: compare it with its larger child, swap if the child wins, and continue down from there until it's bigger than both children or hits a leaf. Cost is O(log n) — the tree's height.

What's the time and space complexity?

O(n log n) in best, average, and worst case, and O(1) extra space (in place). Building the heap is only O(n); the harvest phase contributes the log n.

Heap sort vs quicksort vs merge sort?

Quicksort is usually faster but has an O(n²) worst case. Merge sort is O(n log n) and stable but needs O(n) memory. Heap sort guarantees O(n log n) and sorts in place, but is not stable and less cache-friendly.

RESULT

—

Next → keep the heap around instead of sorting once, and you have a priority queue — the engine inside Dijkstra, A*, and every top-k stream.

Finished this one? 0 / 17 Algorithms done

Explore the topic

See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.

Algorithms & DSA

More Algorithms

Explore more from Vibe Engines

Handbooks →
Roadmaps →
System Designs →
AI System Designs →
Labs →
Paper Breakdowns →