The Binary Heap Structure

Definition

A (binary) max-heap is a complete binary tree satisfying the heap property: the value at every node is greater than or equal to the values of its children. A min-heap reverses this: every node is less than or equal to its children.

Two defining properties:

1. Structural property: The tree is complete — every level except possibly the bottom is full, and the bottom level is filled from left to right.
2. Ordering property: Parent $\ge$ children (max-heap) or Parent $\le$ children (min-heap).

Array Representation

The complete binary tree structure enables a compact array representation. Using 1-indexed arrays:

• Root at $A[1]$.
• Left child of node $i$: $A[2i]$.
• Right child of node $i$: $A[2i + 1]$.
• Parent of node $i$: $A[\lfloor i/2 \rfloor]$.

The root has no parent ($\lfloor 1/2 \rfloor = 0$). A child is absent when $2i$ or $2i + 1$ exceeds A.heap_size (which may be less than A.length since the heap may occupy only a prefix of the array).

Height of a Heap

A heap with $n$ nodes has height $h = \lfloor \log_2 n \rfloor$. The number of nodes at level $k$ is at most $2^k$, and the deepest leaf is at level $h$.

• For $n=6$: $h = \lfloor \log_2 6 \rfloor = \lfloor 2.58 \rfloor = 2$.
• For $n=15$: $h = \lfloor \log_2 15 \rfloor = 3$ (a perfect binary tree).

Operations that traverse from root to leaf (or leaf to root) are bounded by the height, giving $O(\log n)$ time.

Heap vs Binary Search Tree

Property	Heap	BST
Left-right ordering	None; only parent-child inequality	Left subtree < root < right subtree
Structure	Complete tree	No structural guarantee (can be degenerate)
Finding min/max	$O(1)$ — always at root	$O(h)$ — traverse to leftmost/rightmost
Searching	$O(n)$ — must scan	$O(h)$ if balanced
In-order traversal	Not meaningful	Produces sorted order
Use case	Priority queue, Heapsort	Dictionary, ordered map

The heap is a semi-structure: cheaper to maintain than a fully ordered structure, yet sufficient for repeatedly extracting the largest (or smallest) element.

Semi-Structured Nature

In a max-heap of $n$ elements:

• The largest is at exactly one place: the root.
• The second largest is in one of two places: the root’s children.
• The third largest is in one of three places: the other root child, or either child of the second largest.

This “partial-sort” property is what makes heap operations $O(\log n)$ rather than the $O(n \log n)$ cost of full sorting.

Summary

Property	Detail
Structure	Complete binary tree, array representation
Parent at $i$	$\lfloor i/2 \rfloor$
Left child at $i$	$2i$
Right child at $i$	$2i + 1$
Height	$\lfloor \log_2 n \rfloor$
Heap property (max)	$A[i] \ge A[2i], A[2i+1]$
Heap vs BST	Heap: weak order, strong structure; BST: strong order, weak structure