Intuition The one core ideaA heap is just an ordinary array that we pretend is a triangular family tree, where every parent is bigger than its kids — so the biggest number always sits at the very front. Heap sort works by repeatedly grabbing that front champion, parking it at the back, and fixing the tree; do this n
Before you can read the parent note, you need to see the objects it talks about. This page builds every one of them from nothing. Take them in order — each rests on the one above it.
An array is a row of numbered boxes sitting next to each other in memory. Each box holds one value; each box has an index — its position number.
We write the array as A i A [ i ]
Think of lockers in a hallway, numbered starting at 0 0 1 2 the first box is index 0 1 That single convention decides every formula on this page, so lock it in now.
n length of the array = how many boxes there are.The valid indices are therefore 0 , 1 , 2 , … , n − 1 last index is n − 1 not n n
Common mistake The last box isn − 1 n = 5 A [ 0 ] , A [ 1 ] , A [ 2 ] , A [ 3 ] , A [ 4 ] A [ 5 ] end = n-1, it means "point at the genuine last box."
A binary tree is a family diagram where one top node (the root ) can have up to two children, each child can have up to two children, and so on downward.
Picture a tournament bracket drawn upside-down: one champion slot at the top, splitting into two, then four, then eight. "Binary" just means at most two branches per node. The words we borrow from family trees:
root — the topmost node (has no parent).parent — the node directly above another.child — the node directly below (left child / right child).leaf — a node with no children (bottom of a branch).
Why does the topic need a tree at all? Because a plain array has no notion of "bigger than my neighbours above." The tree gives us a direction — up — so we can talk about a single biggest value floating to the top.
Definition Complete binary treeA complete binary tree is one where every level is completely full, except possibly the bottom level , which fills strictly left to right with no gaps.
Intuition Why "complete" mattersA tree normally needs pointers — little arrows in memory saying "my left child lives over there." Pointers cost extra memory. But if the tree has no gaps , we can just lay the nodes out row by row (level 0, then level 1, then level 2…) into the array boxes, and the position alone tells us who is whose child. No arrows needed.
Read the figure top-to-bottom, left-to-right, writing each node into the next array box. The tree and the array are now the same thing , viewed two ways. That equality is the whole reason heap sort is in-place (uses no extra array).
Now that the tree lives in the array, "go to my child" must become a calculation on the index number . For a node at index i
Two new symbols appear here — earn them before using them:
2 i + 1 2 i + 2 ⌊ ⌋ floor brackets.
⌊ x ⌋ ⌊ x ⌋ round down to the nearest whole number." ⌊ 2.9 ⌋ = 2 ⌊ 3.0 ⌋ = 3 ⌊ 0.5 ⌋ = 0
Intuition Why floor is needed hereWhen we divide ( i − 1 ) 2 2.5 2.5 back to the same whole-number parent, so we throw away the fraction. That is exactly what flooring does — it answers the question "which single parent do I belong to?"
Worked example Check the formulas on a small treeTake the root i = 0
left child = 2 ( 0 ) + 1 = 1
right child = 2 ( 0 ) + 2 = 2
Now take node i = 4
parent = ⌊( 4 − 1 ) /2 ⌋ = ⌊ 1.5 ⌋ = 1
Node i = 3 = ⌊( 3 − 1 ) /2 ⌋ = ⌊ 1 ⌋ = 1
So boxes 3 4 both children of box 1
≥ a ≥ b a or equal to b 5 ≥ 3 4 ≥ 4
Definition Max-heap propertyA max-heap is a complete binary tree where every parent is ≥ Nothing is said about left-vs-right order between siblings — only parent-beats-child.
Intuition What this guarantees, and what it does NOTSince each parent outranks its kids, and those kids outrank their kids, the biggest value in the whole heap can only be at one place — the root, index 0 That is the payoff: the champion is always instantly findable at A [ 0 ] not a sorted array. Siblings can be in any order; a value two levels down might be larger than something on a different branch. A heap is "loosely sorted, tightly rooted."
swap( A [ i ] , A [ j ]) : exchange the contents of two boxes. Box i j without a second array.sift-down (a.k.a. heapify ): if a node's value is too small for its position, keep swapping it downward with its larger child until it sits where the heap rule holds. The parent note's inner loop is this verb.
Intuition Picture of sift-downA too-small value at the top is like a heavy diver: it sinks past lighter children level by level until it settles. Each sink is one comparison + one swap, and a complete tree is only about log 2 n log 2 n
log 2 n log 2 n n 1 n n = 8 4 , 2 , 1 log 2 8 = 3
O ( ⋅ ) O ( f ( n )) f ( n ) O ( n log n ) n log n
Intuition Why these two show up together in heap sortWe crown a champion n n log 2 n log n O ( n log n ) see , not just read.
Binary tree root parent child
Index formulas 2i+1 2i+2 floor
Log n height gives O n log n
Cover the right side and answer each aloud before opening the parent note.
In a 0-indexed array of length n n − 1
What does "complete" buy us that lets a tree live in a flat array? No gaps, so position alone encodes parent/child — no pointers, no extra memory.
Left child of node i 2 i + 1
Right child of node i 2 i + 2
Parent of node i ⌊ ( i − 1 ) /2 ⌋
Why is there a floor in the parent formula? Division can give a fraction, but both children must map back to the one whole-numbered parent box, so we round down.
What is ⌊ 3.5 ⌋ 3
State the max-heap property in words. Every parent is greater than or equal to both of its children.
Where does the maximum value always sit in a max-heap? At the root, index 0
Is a heap the same as a sorted array? No — only parent-beats-child holds; siblings are unordered.
What does sift-down do? Sinks a too-small node downward by swapping with its larger child until the heap rule holds.
What does log 2 n The number of levels (height) of a complete tree with n
Why is heap sort O ( n log n ) n log n
Recall Quick self-quizFor n = 16 log 2 16 = 4 7 ⌊ 6/2 ⌋ = 3
