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

This page assumes nothing. Every squiggle, bracket and word the parent note used gets built here from the ground up, in an order where each idea rests on the one before it.

0. What is a "tree" at all?

Before "heap" we need "tree". Forget computers for a second.

The vocabulary the parent note throws around, all read off this one picture:

• root — the single top node. Everything hangs from it. In the figure it's the amber circle.
• child — a node directly below another, connected by one edge.
• parent — the node directly above a child. Every node except the root has exactly one parent.
• sibling — two nodes sharing the same parent (side by side).
• leaf — a node with no children (the bottom fringe).
• level (or depth) — how many edges down from the root you are. Root = level 0, its children = level 1, and so on.
• height — the number of edges on the longest path from root down to a leaf. A short bushy tree has small height.

1. "Binary" — the fan-out is exactly two

Left and right are positions, not sizes — a node can have only a left child, only a right, both, or neither.

2. "Complete" — the shape rule (this is the parent's shape property)

The parent note says a heap is a complete binary tree whose last level fills left to right. Here is what that sentence means as a picture.

• Left tree (cyan): every full level, last level packed left → complete ✓.
• Right tree (amber X): there's a hole on the left of the bottom row while something sits to its right → not complete ✗.

See Complete Binary Tree for more on this shape alone.

3. The heap-order rule and the symbols $\ge$ and $\le$

The parent writes $A[\text{parent}]\ge A[\text{child}]$. Let's earn each piece.

The comparison arrows

• $a\ge b$ reads "$a$ is greater than or equal to $b$". The open mouth of the sign faces the bigger side; the flat line under it adds "or equal". Picture: $a$ sits at least as high as $b$.
• $a\le b$ reads "$a$ is less than or equal to $b$" — the mirror image.

The rule as a picture

4. Reading an array: what $A[i]$ and $n$ mean

The parent suddenly writes things like [9, 5, 8, 1, 4] and $A[\text{parent}]$. Decode:

5. The array trick — turning a tree into a flat row

This is the cleverest hidden move in the parent note. We write the tree into an array by reading it level by level, left to right (this reading order is called level-order).

Because the tree is complete, level-order fills the array with no holes. Now the child/parent lines don't need to be stored — we can compute them.

The floor brackets $\lfloor \cdot \rfloor$ mean "round down to the nearest whole number" — e.g. $\lfloor 2.7\rfloor =2$, $\lfloor 5/2\rfloor =2$. We need it because half of an odd number isn't a whole box number, and box numbers must be whole.

6. Logs, floors and why $O(\log n)$ appears

The parent claims height $=\lfloor {\log }_{2}n\rfloor$ and operations cost $O(\log n)$. Two new symbols.

The logarithm ${\log }_{2}n$

Big-O

$O(\log n)$ is Big-O Notation — a coarse label meaning "grows like $\log n$ as $n$ gets huge, ignoring constant factors." Since fixing a heap walks at most one root-to-leaf path (one path = height = $\log n$ hops), each insert/extract is $O(\log n)$.

7. The two repair moves the parent uses

The parent's worked examples fling around "sift-down" and "sift-up". Name them once, precisely, so the later notes can lean on the terms:

Both walk one vertical path, so both cost $O(\log n)$ — the same log from Section 6.

Prerequisite map

Equipment checklist

Cover the right side; you're ready when each answer comes instantly.