A binary heap is one of the most elegant and efficient data structures in computer science. It serves as the primary backing engine for priority queues, powers Dijkstra's shortest path algorithm and Prim's minimum spanning tree algorithm, and provides the foundation for heapsort—an optimal O(n log n) in-place comparison sort.
In core US computer science courses such as UC Berkeley CS 61B, MIT 6.1210, and Stanford CS 161, binary heaps are an essential exam and homework topic. Instructors test whether students can translate between contiguous array indices and tree levels, execute sift-up and sift-down operations without skipping comparisons, and explain why bottom-up heap construction runs in linear time.
This guide walks through binary heap mechanics from the ground up: the complete tree shape invariant, array index arithmetic, step-by-step min-heap and max-heap traces computed directly from ToolSphere's data structure library, the heapsort connection, and complete Big-O time and space complexity.
Complete Binary Tree and Array Representation
A binary heap is a complete binary tree that satisfies the heap-order property.
- Complete binary tree shape: Every level of the tree is completely filled, except possibly the bottom level, which is filled strictly from left to right with no gaps.
- Contiguous array storage: Because the tree has no missing intermediate nodes, it requires zero pointers. The entire tree is stored in a single contiguous array.
Tree Level Node Count Array Indices (0-Indexed)
Level 0 1 node [0]
Level 1 2 nodes [1, 2]
Level 2 4 nodes [3, 4, 5, 6]
Level 3 8 nodes [7, 8, 9, 10, 11, 12, 13, 14]
Level h 2^h nodes [2^h - 1 ... 2^(h+1) - 2]
Zero-Indexed Array Formulas
For any node located at array index i:
- Parent index:
parent(i) = floor((i - 1) / 2)(for alli > 0) - Left child index:
left(i) = 2 * i + 1 - Right child index:
right(i) = 2 * i + 2 - Has left child:
2 * i + 1 < n(wherenis the current heap size) - Has right child:
2 * i + 2 < n - Is a leaf node:
2 * i + 1 >= n(all indices fromfloor(n / 2)ton - 1are leaves)
Note on 1-indexed textbooks: Older textbooks (such as earlier editions of CLRS) sometimes describe heaps using 1-based indexing, where parent(i) = floor(i / 2), left(i) = 2i, and right(i) = 2i + 1. Modern production code in Python (heapq), Java (PriorityQueue), C++ (std::priority_queue), and JavaScript uses 0-based arrays, which makes the formulas above standard.
The Heap-Order Invariant: Min-Heap vs Max-Heap
Binary heaps come in two complementary flavors:
- Min-Heap Property: For every node
i > 0,A[parent(i)] <= A[i]. Every parent is less than or equal to its children. Consequently, the minimum element of the entire collection always sits at the root (A[0]). - Max-Heap Property: For every node
i > 0,A[parent(i)] >= A[i]. Every parent is greater than or equal to its children. Consequently, the maximum element always sits at the root (A[0]).
Crucial Difference: Heap vs Binary Search Tree (BST)
Students often confuse binary heaps with binary search trees. The key distinction lies in the ordering axis:
- BST ordering is horizontal (symmetric): For every node, all keys in its left subtree are smaller, and all keys in its right subtree are larger (
left < root < right). - Heap ordering is vertical (hierarchical): An ancestor is always smaller (in a min-heap) or larger (in a max-heap) than its descendants. There is no relationship between left and right siblings. A left child may be larger, smaller, or equal to its right sibling.
Because of this vertical-only constraint, searching for an arbitrary key in an unsorted binary heap requires an O(n) linear scan, whereas finding the extreme element (min or max) takes instant O(1) time.
Min-Heap Insert: Sift Up (Percolate Up)
When inserting a new key into a min-heap:
- Append: Place the new element at the very end of the array (at index
k = n), which corresponds to the first open leaf position on the bottom level from left to right. This preserves the complete tree shape invariant. - Compare with parent: If
k == 0, the element is at the root and we stop. Otherwise, compute parent indexp = floor((k - 1) / 2). - Sift up if smaller: If
A[k] < A[p], swapA[k]withA[p], setk = p, and repeat step 2. - Terminate: The process stops as soon as
A[p] <= A[k]ork == 0.
Worked Example: Building a Min-Heap
We trace the insertion of the 7-element sequence used across ToolSphere's Data Structure Visualizer:
Keys to insert: [30, 20, 10, 25, 28, 40, 50]
Every comparison and swap below is computed directly by src/lib/ds/structures.ts.
Step 1: Insert 30
- Append 30 at index 0. It is the root.
- Array:
[30] - Tree:
30
Step 2: Insert 20
- Append 20 at index 1.
- Compare child 20 (index 1) with parent 30 (index 0).
- Since
20 < 30, sift up: swap 20 and 30. - Array:
[20, 30] - Tree:
20 / 30
Step 3: Insert 10
- Append 10 at index 2.
- Compare child 10 (index 2) with parent 20 (index 0).
- Since
10 < 20, sift up: swap 10 and 20. - Array:
[10, 30, 20] - Tree:
10 / \ 30 20
Step 4: Insert 25
- Append 25 at index 3.
- Compare child 25 (index 3) with parent 30 (index 1).
- Since
25 < 30, sift up: swap 25 and 30. - Compare child 25 (index 1) with root parent 10 (index 0).
- Since
10 <= 25, the min-heap condition holds. Sift up terminates. - Array:
[10, 25, 20, 30] - Tree:
10 / \ 25 20 / 30
Step 5: Insert 28
- Append 28 at index 4.
- Compare child 28 (index 4) with parent 25 (index 1).
- Since
25 <= 28, parent is smaller. Sift up terminates immediately with zero swaps. - Array:
[10, 25, 20, 30, 28] - Tree:
10 / \ 25 20 / \ 30 28
Step 6: Insert 40
- Append 40 at index 5.
- Compare child 40 (index 5) with parent 20 (index 2).
- Since
20 <= 40, parent is smaller. Sift up terminates immediately. - Array:
[10, 25, 20, 30, 28, 40] - Tree:
10 / \ 25 20 / \ / 30 28 40
Step 7: Insert 50
- Append 50 at index 6.
- Compare child 50 (index 6) with parent 20 (index 2).
- Since
20 <= 50, parent is smaller. Sift up terminates immediately. - Final Array:
[10, 25, 20, 30, 28, 40, 50] - Final Tree:
10 / \ 25 20 / \ / \ 30 28 40 50
Notice that on the final 3 insertions, no swaps were needed because the newly added values were already larger than their parents. In practice, the average insertion into a binary heap requires only ~1.6 comparisons and often zero swaps!
Min-Heap Delete-Min: Sift Down (Sink)
Extracting the minimum element from a min-heap requires removing the root (A[0]). However, leaving an empty hole at the root would disconnect the tree into two separate subtrees. To preserve the complete binary tree structure with zero pointer overhead, we use the standard extraction procedure:
- Save root: Record
A[0]as the return value. - Move last element to root: Pop the last element from index
n - 1and place it at index 0. The tree size shrinks by 1. - Compare children: At current index
k, check its children:left = 2 * k + 1andright = 2 * k + 2.- If no children exist (
left >= n), terminate. - If only a left child exists, let
smaller = left. - If both children exist, pick
smaller = A[left] <= A[right] ? left : right.
- If no children exist (
- Sift down if violated: If
A[k] > A[smaller], swapA[k]withA[smaller], updatek = smaller, and repeat step 3. - Terminate: Stop when
A[k] <= A[smaller]orkreaches a leaf.
Worked Example: Deleting from the Min-Heap
Starting with our 7-node min-heap: [10, 25, 20, 30, 28, 40, 50].
Extraction 1: Delete-Min (Extract 10)
- Save root 10.
- Pop the last element 50 and overwrite index 0.
- Temporary array:
[50, 25, 20, 30, 28, 40]. - Sift Down at index 0 (value 50):
- Left child is 25 (index 1), right child is 20 (index 2).
- Compare children: 20 is smaller than 25 (
smaller = index 2). - Compare parent 50 with child 20:
50 > 20. - Swap 50 and 20.
- Intermediate array:
[20, 25, 50, 30, 28, 40].
- Sift Down at index 2 (value 50):
- Left child is 40 (index 5). Right child
2 * 2 + 2 = 6is out of bounds. - Only child is 40 (
smaller = index 5). - Compare parent 50 with child 40:
50 > 40. - Swap 50 and 40.
- Intermediate array:
[20, 25, 40, 30, 28, 50].
- Left child is 40 (index 5). Right child
- Sift Down at index 5 (value 50):
- Index 5 has no children (
2 * 5 + 1 = 11 >= 6). Sift down terminates.
- Index 5 has no children (
- Resulting Min-Heap:
- Array:
[20, 25, 40, 30, 28, 50] - Tree:
20 / \ 25 40 / \ / 30 28 50
- Array:
Extraction 2: Delete-Min (Extract 20)
- Save root 20.
- Pop the last element 50 and overwrite index 0.
- Temporary array:
[50, 25, 40, 30, 28]. - Sift Down at index 0 (value 50):
- Left child is 25 (index 1), right child is 40 (index 2).
- Compare children: 25 < 40 (
smaller = index 1). - Compare parent 50 with child 25:
50 > 25. - Swap 50 and 25.
- Intermediate array:
[25, 50, 40, 30, 28].
- Sift Down at index 1 (value 50):
- Left child is 30 (index 3), right child is 28 (index 4).
- Compare children: 28 < 30 (
smaller = index 4). - Compare parent 50 with child 28:
50 > 28. - Swap 50 and 28.
- Intermediate array:
[25, 28, 40, 30, 50].
- Resulting Min-Heap:
- Array:
[25, 28, 40, 30, 50] - Tree:
25 / \ 28 40 / \ 30 50
- Array:
Extraction 3: Delete-Min (Extract 25)
- Save root 25.
- Pop last element 50 and place at root.
- Temporary array:
[50, 28, 40, 30]. - Children of index 0 are 28 (index 1) and 40 (index 2). Smaller child is 28.
50 > 28: Swap 50 and 28 ->[28, 50, 40, 30].- At index 1 (value 50), left child is 30 (index 3).
50 > 30: Swap 50 and 30 ->[28, 30, 40, 50].- Resulting Min-Heap:
- Array:
[28, 30, 40, 50] - Tree:
28 / \ 30 40 / 50
- Array:
Max-Heap Insert and Delete-Max Step by Step
In a max-heap, the root contains the maximum element, and each parent must be greater than or equal to both of its children (A[p] >= A[child]).
Max-Heap Insertions (Same Sequence)
We trace the insertion of [30, 20, 10, 25, 28, 40, 50] into an empty max-heap:
1. Insert 30
- Root node:
[30]
2. Insert 20
- Append at index 1. Parent is 30 (index 0).
30 >= 20: Valid max-heap. No swap.- Array:
[30, 20]
3. Insert 10
- Append at index 2. Parent is 30 (index 0).
30 >= 10: Valid max-heap. No swap.- Array:
[30, 20, 10]
4. Insert 25 (Triggers Sift Up)
- Append at index 3. Parent is 20 (index 1).
25 > 20: Sift up, swap 25 and 20.- Now at index 1. Parent is 30 (index 0).
30 >= 25: Parent is larger. Stop.- Array:
[30, 25, 10, 20] - Tree:
30 / \ 25 10 / 20
5. Insert 28 (Triggers Sift Up)
- Append at index 4. Parent is 25 (index 1).
28 > 25: Sift up, swap 28 and 25.- Now at index 1. Parent is 30 (index 0).
30 >= 28: Parent is larger. Stop.- Array:
[30, 28, 10, 20, 25] - Tree:
30 / \ 28 10 / \ 20 25
6. Insert 40 (Promotes to Root)
- Append at index 5. Parent is 10 (index 2).
40 > 10: Sift up, swap 40 and 10.- Now at index 2. Parent is 30 (index 0).
40 > 30: Sift up, swap 40 and 30.- Element 40 reaches the root. Stop.
- Array:
[40, 28, 30, 20, 25, 10] - Tree:
40 / \ 28 30 / \ / 20 25 10
7. Insert 50 (Promotes to Root)
- Append at index 6. Parent is 30 (index 2).
50 > 30: Sift up, swap 50 and 30.- Now at index 2. Parent is 40 (index 0).
50 > 40: Sift up, swap 50 and 40.- Element 50 becomes the new root of the entire max-heap!
- Final Array:
[50, 28, 40, 20, 25, 10, 30] - Final Tree:
50 / \ 28 40 / \ / \ 20 25 10 30
Max-Heap Delete-Max (Extract 50)
Starting from [50, 28, 40, 20, 25, 10, 30]:
- Save root 50.
- Move last element 30 to index 0: temporary
[30, 28, 40, 20, 25, 10]. - At index 0 (value 30):
- Children are 28 (index 1) and 40 (index 2).
- In a max-heap, pick the larger child:
max(28, 40) = 40(index 2). 30 < 40: Swap 30 and 40.- Intermediate array:
[40, 28, 30, 20, 25, 10].
- At index 2 (value 30):
- Left child is 10 (index 5).
- Compare parent 30 with child 10:
30 >= 10. - Max-heap property holds. Sift down terminates!
- Resulting Max-Heap:
- Array:
[40, 28, 30, 20, 25, 10] - Tree:
40 / \ 28 30 / \ / 20 25 10
- Array:
The Heapsort Connection
The max-heap provides the foundation for Heapsort, one of the canonical comparison sorting algorithms. Heapsort sorts an array of n elements in-place with zero auxiliary memory in two distinct phases:
Phase 1: Build-Heap (Floyd's Linear-Time Algorithm)
Given an arbitrary, unsorted array of n elements, we can convert it into a valid max-heap:
- Naive approach (Repeated Insertions): Insert each element into an initially empty heap. Inserting
nelements with up to O(log n) sifts each takes O(n log n) time. - Floyd's bottom-up method: Observe that all elements from index
floor(n / 2)ton - 1are leaves. A leaf is already a valid 1-node heap! We simply iterate backward from the last non-leaf node down to the root, calling sift-down on each:for i = floor(n / 2) - 1 down to 0: sift_down(A, i, n)
Why Floyd's buildHeap is O(n), Not O(n log n)
This is a standard US exam question (CLRS Section 6.3). The intuition is simple:
- Most nodes in a tree sit near the bottom. Half the nodes (
n / 2) are leaves and do zero work. - A quarter of the nodes (
n / 4) have height 1 and do at most 1 swap. - An eighth of the nodes (
n / 8) have height 2 and do at most 2 swaps. - Only 1 node (the root) has height
log nand can dolog nswaps.
Summing the cost across all heights h from 0 to floor(log n):
Total Swaps <= Sum from h=0 to floor(log n) of (n / 2^(h+1)) * h
= (n / 2) * Sum from h=0 to infinity of (h / 2^h)
= (n / 2) * 2
= n
Because the geometric series converges to 2, the total number of swaps is bounded by n. Bottom-up heap construction runs in strict O(n) linear time!
Phase 2: In-Place Sorting Loop
Once the array is a max-heap, sorting proceeds by repeatedly extracting the maximum:
- Swap
A[0](the maximum element) withA[end], whereendstarts atn - 1. - The largest element is now locked into its final, sorted position at the end of the array.
- Decrement the active heap boundary:
heap_size = heap_size - 1. - Call
sift_down(A, 0, heap_size)to restore the max-heap property for the remaining prefix0 ... end - 1. - Repeat until
heap_size == 1.
Initial Max-Heap: [50, 28, 40, 20, 25, 10, 30]
1. Swap 50 and 30: [30, 28, 40, 20, 25, 10 | 50]
Sift down 30: [40, 28, 30, 20, 25, 10 | 50]
2. Swap 40 and 10: [10, 28, 30, 20, 25 | 40, 50]
Sift down 10: [30, 28, 10, 20, 25 | 40, 50]
3. Swap 30 and 25: [25, 28, 10, 20 | 30, 40, 50]
Sift down 25: [28, 25, 10, 20 | 30, 40, 50]
... Continue until array is fully sorted in ascending order:
Final Array: [10, 20, 25, 28, 30, 40, 50]
Heapsort Properties
- Time Complexity: O(n log n) in all cases (worst, best, and average). Unlike Quicksort, it has no O(n^2) worst case.
- Space Complexity: O(1) auxiliary space (true in-place sort).
- Stability: Not stable. Long-distance swaps between index 0 and index
endcan invert the relative order of identical keys.
Big-O Time and Space Complexity Summary
| Operation | Best Case | Average Case | Worst Case | Space (Auxiliary) | Explanation |
|---|---|---|---|---|---|
| Peek (Find-Min / Find-Max) | O(1) | O(1) | O(1) | O(1) | Always located directly at index 0 |
| Insert (Sift Up) | O(1) | O(1) | O(log n) | O(1) | Average ~1.6 steps; worst path from leaf to root |
| Delete-Min / Delete-Max | O(log n) | O(log n) | O(log n) | O(1) | Sifts down along the height of the tree |
| Build-Heap (Floyd's bottom-up) | O(n) | O(n) | O(n) | O(1) | Sum of heights converges to linear bound |
| Build-Heap (Repeated Inserts) | O(n) | O(n log n) | O(n log n) | O(1) | Suboptimal construction approach |
| Search for Arbitrary Key | O(1) | O(n) | O(n) | O(1) | Requires linear scan; no horizontal ordering |
| Arbitrary Delete (known index) | O(1) | O(log n) | O(log n) | O(1) | May sift up or down from arbitrary position |
| Heapsort | O(n log n) | O(n log n) | O(n log n) | O(1) | O(n) build + n extractions of O(log n) each |
Frequently Asked Questions
Why is a binary heap stored in an array instead of linked tree nodes?
Because a binary heap is guaranteed to be a complete binary tree, there are no missing nodes between index 0 and n - 1. Storing nodes in an array eliminates 16 to 24 bytes of pointer overhead per node (left, right, and parent references in 64-bit architectures) and delivers optimal CPU cache locality. Moving between parent and child is a single multiplication or bit-shift.
What is the difference between a binary heap and a binary search tree (BST)?
A BST maintains horizontal ordering (left < root < right), allowing O(log n) searches for any arbitrary key, but requires complex rebalancing (such as AVL or Red-Black rotations) to avoid degrading to an O(n) linked list. A binary heap maintains only vertical ordering (parent <= child), has zero pointer overhead, guarantees an O(1) extreme value lookup, and cannot degenerate in shape because completeness is enforced on every operation.
Why does Floyd's buildHeap run in O(n) time while repeated insertions take O(n log n)?
When inserting keys one by one, the vast majority of nodes are leaves that may sift up through the full height of the tree (O(log n) work each). In Floyd's bottom-up method, leaves do 0 work, nodes 1 level above leaves do at most 1 swap, and only the root does O(log n) work. Weighting each level by its node count yields a converging geometric sum bounded by 2n.
Can a binary heap contain duplicate values?
Yes. The heap-order property is non-strict (<= for min-heaps, >= for max-heaps). Multiple identical keys can reside anywhere along different ancestor-descendant paths without violating the invariant.
Why is heapsort not a stable sorting algorithm?
A sorting algorithm is stable if equal elements retain their original relative order. In heapsort, extracting elements involves swapping the root with the last leaf element in the heap array. This long-distance swap can jump equal elements across one another, breaking initial ordering.
When should you use a min-heap versus a max-heap?
Use a min-heap when you repeatedly need the smallest element, such as in Dijkstra's shortest path algorithm (finding the unvisited vertex with smallest tentative distance) or Huffman coding (merging the two lowest-frequency trees). Use a max-heap when you need the largest element or when sorting an array in ascending order with in-place heapsort.
How does a binary heap implement an abstract Priority Queue?
An abstract Priority Queue (PQ) interface defines three primary methods: insert(key, priority), extractMin() (or extractMax()), and peek(). A binary heap implements peek() in O(1) time by returning A[0], insert() in O(log n) time via sift-up, and extractMin() in O(log n) time via sift-down.
What happens during an arbitrary key deletion in a binary heap?
To delete a key at arbitrary index k: replace A[k] with the last element A[n - 1], decrement heap size, and compare the replacement value with its parent and children. If the value is smaller than its parent (in a min-heap), it must sift up; if larger than its smaller child, it must sift down.
Why does 0-based indexing use 2i + 1 and 2i + 2 while 1-based indexing uses 2i and 2i + 1?
In a 1-based array, shifting index bits left by 1 (i << 1) corresponds to multiplying by 2, which gives the left child 2i. In 0-based arrays, the root is at index 0, where 2 * 0 = 0, which would collide with the parent. Adding 1 shifts the left child to 2i + 1, and the right child to 2i + 2.
Is an array that is sorted in ascending order always a min-heap?
Yes. If an array is sorted in ascending order (A[0] <= A[1] <= A[2] <= ... <= A[n-1]), then for any index i, its parent floor((i - 1) / 2) has an index strictly less than i. Because the array is non-decreasing, A[parent(i)] <= A[i] is guaranteed for all i > 0.
Use the Data Structure Visualizer to trace tree and heap operations. Use the Graph Algorithm Visualizer to explore graph algorithm steps. For a related walkthrough, read AVL Tree Rotations Explained: LL, RR, LR, RL.