Heap — max-heap and min-heap properties: Visual walkthrough

We use a max-heap throughout (biggest on top). Everything flips symmetrically for a min-heap, and we point out exactly where.

Step 1 — Start with the shape: a tree with no gaps

WHAT. Draw circles (call them nodes), each holding a number. Connect each node to at most two nodes below it (its children). The single node at the very top with no node above it is the root.

WHY this shape and not any tree? We want the tree to be as shallow as possible, because later every operation walks from top to bottom. A tree is shallowest when we never leave a hole: we fill each level completely, top to bottom, and inside a level we fill left to right. A tree filled this way is called a complete binary tree (see Complete Binary Tree).

PICTURE. Look at the figure. The black nodes are placed in reading order — left to right, then drop a level. There is no gap anywhere before the last node.

Figure — Heap — max-heap and min-heap properties

Step 2 — Read the tree into a flat array

WHAT. Number the nodes in that same reading order: root is $0$ , its two children are $1$ and $2$ , the next level is $3, 4, 5, 6$ , and so on. Now just store the values in a plain list at those numbered positions.

WHY an array and not pointer-linked nodes? Because there are no gaps (Step 1 guaranteed that), every slot $0, 1, 2, \dots, n - 1$ is used. A gapless numbering means we never waste a slot, so a contiguous array holds the whole tree — no node objects, no pointers, and it sits nicely in cache.

PICTURE. The red arrows trace the reading order that maps each tree node onto one array cell. The tree above and the strip below hold the same data.

Step 3 — Derive the child and parent formulas by counting slots

WHAT. We want, for a node at index $i$ , the indices of its left child, right child, and parent — using only arithmetic.

WHY count slots? Because the numbering is just "how many nodes come before me." If we count how many child-slots are used up before node $i$ 's own children, we land exactly on the child's index. This is pure counting — no geometry needed, but the picture makes the count visible.

The count, term by term. Nodes $0, 1, \dots, i - 1$ come before node $i$ — that is $how many earlier nodes i$ nodes. Each earlier node owns exactly $two children each 2$ child-slots, so $2 i$ child-slots are filled before node $i$ 's children begin. The root occupied $1$ slot (index $0$ ) that isn't anyone's child, which shifts everything by one. Putting it together:

$left (i) = child-slots before us 2 i + skip root’s own slot 1, right (i) = 2 i + 2$

To get the parent, we undo the child formula. If some node is a left child, $child = 2 i + 1$ , so $i = \frac{child - 1}{2}$ . If it's a right child, $child = 2 i + 2$ , so $i = \frac{child - 2}{2}$ . Both collapse to one formula once we round down:

$parent (c) = ⌊ \frac{c - 1}{2} ⌋$

where $⌊ \cdot ⌋$ means "round down to the nearest whole number" — it swallows the difference between the $- 1$ and $- 2$ cases.

PICTURE. The red braces show the block of $2 i$ child-slots sitting before node $i$ 's children; the arrow lands on $2 i + 1$ .

Step 4 — Add the value rule: parent beats child, everywhere

WHAT. Now impose the heap-order property: for every parent–child pair, $A [parent] \geq A [child] (max-heap) .$ Each symbol: $A [\cdot]$ is "the value stored at that index," $\geq$ is "greater than or equal to." For a min-heap, flip the single symbol to $\leq$ .

WHY only parent vs child, not everything? Because we only ever need one fast answer: what is the biggest element? If every parent dominates its own children, then by following "bigger than" links upward, the very top must be the biggest of all — so the maximum sits at the root and peeking costs $O (1)$ . We deliberately do not compare siblings, because ordering siblings would cost work we never cash in.

PICTURE. Green-highlighted (here red-accent) edges are the checked relations — each parent to each child. Notice the two children of a node are not connected to each other: siblings are unordered.

Step 5 — Why the tree is short: the height bound

WHAT. Count how many nodes fit in a complete tree of height $h$ (height = number of edges on the longest root-to-leaf path).

WHY do we care about height? Because every fix we do (Step 6) walks one root-to-leaf path. If height is small, every operation is fast. So we must prove height is small.

The count. Level $0$ has $1$ node, level $1$ has $2$ , level $2$ has $4$ — level $k$ has $2^{k}$ . A tree of height $h$ has at least the root of the last level (so $2^{h}$ nodes, when the last level holds just $1$ ) and at most a completely full last level:

$last level barely started 2^{h} \leq n \leq every level full 2^{h + 1} - 1$

Taking $lo g_{2}$ of the left inequality gives $h \leq lo g_{2} n$ , and the right gives $h > lo g_{2} n - 1$ , pinning it to

$h = ⌊ lo g_{2} n ⌋ .$

Here $lo g_{2} n$ answers "how many times can I double $1$ before reaching $n$ ?" — exactly the number of levels. See Big-O Notation for why this makes operations $O (lo g n)$ .

PICTURE. The red path is the longest root-to-leaf walk; its length grows like $lo g_{2} n$ as the tree widens.

Step 6 — Insert an element: append, then sift-up

WHAT. To add a value, place it in the next free array slot (the next leaf), then repeatedly compare it with its parent and swap up while it is too extreme for its spot.

WHY append first? The only slot that keeps the tree complete (Step 1) is the next empty leaf — filling any other spot would leave a gap. So shape forces the landing spot; then we repair order.

WHY compare with the parent, not children? A freshly appended value may be bigger than its parent (in a max-heap) — it is too big for a low position. Swapping with the parent moves it toward the root, exactly the direction a too-big value should travel.

PICTURE. We insert $10$ into the max-heap [9, 8, 7, 5, 4]. The red node is the traveller; each panel shows one swap up its ancestor path.

Trace it:

Append $10$ at index $5$ . $parent (5) = ⌊ 4/2 ⌋ = 2$ , value $7$ . Is $7 \geq 10$ ? No → swap. Array [9,8,10,5,4,7].
Now $10$ is at index $2$ . $parent (2) = ⌊ 1/2 ⌋ = 0$ , value $9$ . Is $9 \geq 10$ ? No → swap. Array [10,8,9,5,4,7].
Index $0$ is the root → stop. $10$ is now the max on top.

Step 7 — The mirror case (sift-down) and the degenerate cases

WHAT. The opposite of insert: if a value is too small for a high position (e.g. after we overwrite the root), push it down. Compare with the larger child and swap while a child beats it. This is max-heapify, the engine of Build-Heap (Heapify) O(n) and Heapsort.

WHY swap with the larger child? After the swap, the promoted child becomes the new parent — it must dominate the other child too. Only the larger child is guaranteed to be $\geq$ its sibling, so swapping with it keeps the rule intact automatically.

Degenerate cases you must never hit unprepared:

Only one child. A node whose right index $2 i + 2 \geq n$ has just a left child — compare against that one only. (Example 1 in the parent, $i = 2$ , skips index $6$ .)
Leaf node. If $2 i + 1 \geq n$ , the node has no children — sift-down stops instantly.
$n = 0$ (empty) or $n = 1$ (root only). No parent–child pairs exist, so any such array is trivially a valid heap — nothing to check.
Equal values. $A [parent] = A [child]$ satisfies both $\geq$ and $\leq$ , so ties never cause a swap; duplicates are perfectly legal.

PICTURE. Root $3$ in [3,9,8,5,4] sifts down. The red node is the sinking value; note we always pick the larger child (highlighted).

Trace it: $i = 0$ val $3$ , children $9, 8$ → larger is $9$ (index $1$ ), $3 < 9$ swap → [9,3,8,5,4]. Now $i = 1$ val $3$ , children $5, 4$ → larger $5$ (index $3$ ), $3 < 5$ swap → [9,5,8,3,4]. Index $3$ is a leaf → stop. Valid max-heap.

The one-picture summary

Everything on one canvas: the shape (complete tree, no gaps) ↔ the array (via $2 i + 1, 2 i + 2, ⌊(i - 1) /2 ⌋$ ), the order rule on every parent–child edge, and the two repair motions — sift-up for insert, sift-down for heapify — each walking one path of length $⌊ lo g_{2} n ⌋$ .

Recall Feynman retelling — the whole walkthrough in plain words

We started by drawing a tree that never leaves a hole — fill each row completely, left to right. Because there are no holes, we can just list the nodes in reading order into an ordinary array, and a little counting tells us that a node at spot $i$ has its kids at $2 i + 1$ and $2 i + 2$ , and its parent at $⌊(i - 1) /2 ⌋$ . Then we added one rule: every parent must be at least as big as its children — but we never compare two kids to each other, so the array is not fully sorted; only the boss-beats-subordinate chains hold. That one rule forces the biggest number to the very top, so peeking is instant. Since each row doubles, a tree of $n$ nodes is only about $lo g_{2} n$ rows tall. When a newcomer arrives it stands at the next empty spot (to keep the shape), then keeps swapping upward with its boss until someone above is bigger — a short climb because the tree is short. The reverse move, when a too-small value sits too high, is to sink it down, always swapping with the bigger child so the new boss still beats the other kid. Edge cases: a node with one child, a leaf, an empty or single-element array, and ties — all handled by the same rule doing nothing surprising.

Connections

3.4.10 Heap — max-heap and min-heap properties (Hinglish) — the parent topic (Hinglish).
Complete Binary Tree — the no-gap shape from Step 1.
Priority Queue — cashes in the fast insert/extract.
Build-Heap (Heapify) O(n) — repeated sift-down (Step 7).
Heapsort — build-heap then extract the root repeatedly.
Binary Search Tree — contrast: BST does order siblings.
Big-O Notation — why one path = $O (lo g n)$ .