Foundations — Heap sort — in-place, O(n log n)

Before you can read the parent note, you need to own every symbol it throws at you. We build them one at a time, each on top of the last. Nothing appears before it is drawn.

1. What is an array? (the row of boxes)

The little number $i$ is called the index — it is just the label on the box, like a house number on a street. We start counting at $0$, not $1$. So the first box is $A[0]$, the second is $A[1]$, and so on. This "start at zero" habit is called 0-based indexing and every formula in the parent note assumes it.

Why an array and not a bag of numbers? Because a box has a fixed address. If I know box $5$ exists, I can jump straight to it — no searching. That instant jump ("random access") is the whole reason heap sort can be fast and use no extra memory.

2. What is a tree? (boxes that point to boxes)

Picture a family tree drawn upside-down: the ancestor (root) is at the top, descendants fan out below.

The word binary just means "two" — at most two children each. See Complete Binary Tree for the exact shape we need, which we build next.

3. The "complete" shape (no holes)

Why do we insist on this tidy shape? Because a tree with no holes can be flattened into an array with zero wasted boxes. Read the tree level by level, left to right, and drop each node into the next array box. That mapping is the bridge between "tree" (easy to think about) and "array" (cheap to store).

Look at the figure: the tree on the left and the row on the right hold the same numbers in the same slots. The parent calls this the "array form" of a heap.

4. The index arithmetic (parent ↔ child by formula)

Here is the payoff of the complete shape. Because there are no gaps, the position of any child or parent can be computed — no pointers, no arrows stored anywhere. For a box at index $i$:

Two new symbols appear here, so we define them before using them:

Why floor? A parent is one box; two different children (left and right) both point back to it. Floor division squashes both "$(i-1)/2$" answers onto the same whole number, so one formula recovers the parent no matter which child you started from.

Trace it in the figure of §3: box $0$'s left child is $2(0)+1=1$, right child is $2(0)+2=2$. Box $1$'s parent is $\lfloor (1-1)/2\rfloor =\lfloor 0\rfloor =0$. It closes the loop. ✔

5. The heap property (biggest floats up)

The symbol $\ge$ reads "at least as big as." Because every parent beats its children, and the chain of parents leads up to the root, the root box $A[0]$ always holds the maximum of the whole array. That single fact is the engine of the entire sort.

Note what the heap property does not say: it says nothing about left-vs-right, and nothing about cousins. A heap is only loosely sorted — just enough for the top to always be the biggest. Contrast this with Binary Heap (the full structure) and Priority Queue (its most common use).

6. Big-O — what "$O(n\log n)$" even means

The parent's headline is $O(n\log n)$. Three symbols to unpack.

Why $\log$ and not something else here? Because the work per number is one walk down the tree, and the tree's depth is $\log n$. The tool matches the shape: trees halve, logs count halvings. For how this compares to Merge Sort, Quicksort, and Introsort, see the parent.

7. Swap and "in-place"

This is why the whole page kept insisting on "no pointers, index arithmetic": every trick was chosen so the sort could run inside one row of boxes.

Prerequisite map

Read it bottom-of-arrow to top: arrays and trees feed the complete tree, which unlocks the index formulas, which power the max-heap; that plus swapping and the Big-O vocabulary is exactly what the parent note assumes you already own.

Equipment checklist