Source: CS 225 Slide Deck, UIUC
Tags: heap, min-heap, max-heap, priority queue, binary heap, buildHeap, heapifyUp, heapifyDown, heap sort, array-based tree, complete binary tree, CS 225, data structures
Difficulty: Intermediate Prerequisites: Binary trees, array representations of trees, Big-O notation.
Heaps are a specialised tree-based structure used whenever you need fast access to the minimum (or maximum) element in a collection. They sit at the heart of priority queues, which turn up everywhere from operating system schedulers to graph algorithms like Dijkstra's. You should already be comfortable with binary trees and how complete trees map onto arrays before working through this material.
A heap is a complete binary tree stored in an array where every parent satisfies an ordering property relative to its children. Building a heap from an unsorted array can be done in O(n) time using heapifyDown, and repeatedly extracting the root gives you heap sort in O(n log n).
Min-heap
A complete binary tree in which every node's value is less than or equal to the values of its children. The smallest element is always at the root. Think of it as: the boss is always smaller than everyone who reports to them, all the way down the org chart.
Max-heap
The mirror image of a min-heap. Every node's value is greater than or equal to its children's values, so the largest element sits at the root.
Complete binary tree
A binary tree in which every level is fully filled except possibly the last, and the last level is filled from left to right with no gaps. In simple terms, you fill the tree row by row, left to right, never skipping a spot.
Heap property (heap-order property)
The constraint that defines a heap. In a min-heap, parent <= children. In a max-heap, parent >= children. This property must hold for every node.
heapifyUp (percolate up / sift up / bubble up)
The operation used after inserting a new element at the bottom of the heap. You compare the new node with its parent and swap upward until the heap property is restored.
heapifyDown (percolate down / sift down / bubble down)
The operation used after removing the root or during buildHeap. You compare a node with its children and swap it with the smaller child (min-heap) or larger child (max-heap) until the heap property is restored.
buildHeap
The process of converting an arbitrary, unsorted array into a valid heap. There are three common strategies, each with different running times.
Heap sort
A comparison-based sorting algorithm that first builds a heap from the data, then repeatedly extracts the root to produce sorted output.
A binary heap is stored as a flat array. The root sits at index 1 (index 0 is typically left empty for arithmetic convenience).
For a node at index i:
Left child: 2 * i
Right child: 2 * i + 1
Parent: i / 2 (integer division)
Because the tree is complete, there are no gaps in the array. This gives O(1) access to any node's parent or children with simple arithmetic, no pointers needed.
Consider the array: [_, 4, 5, 6, 15, 9, 7, 20, 16, 25, 14, 12, 11] (index 0 unused).
The tree reads as:
Root: 4
Level 1: 5, 6
Level 2: 15, 9, 7, 20
Level 3: 16, 25, 14, 12, 11
Every parent is smaller than its children, confirming the min-heap property.
Place the new element at the next available position (end of the array).
Compare it with its parent.
If it is smaller (min-heap), swap with the parent.
Repeat until the heap property holds or the root is reached.
Running time: O(log n), since the tree height is floor(log₂ n).
Replace the root with the last element in the array.
Reduce the size by one.
Compare the new root with its children.
Swap with the smaller child (min-heap) if the heap property is violated.
Repeat down the tree until the property is restored.
Running time: O(log n).
Given an unsorted array (illustrated with the letters B, U, I, L, D, H, E, A, P, N, O, W):
Strategy 1 – Sort the array
Sort the array first. A sorted array is already a valid min-heap because every parent will be smaller than both children. Running time: O(n log n) (dominated by the sort).
Strategy 2 – Repeated heapifyUp
Start from index 2 and heapifyUp each element, one at a time, as though you were inserting elements into an initially empty heap.
template Running time: O(n log n). Each of the n elements may travel up to log n levels.
Strategy 3 – Repeated heapifyDown (Floyd's algorithm)
Start from the last internal node (parent of the last leaf) and heapifyDown each node back to the root.
template Running time: O(n). This is the optimal strategy and the one most commonly meant by "buildHeap."
The proof defines S(h) as the sum of the heights of all nodes in a complete tree of height h. HeapifyDown on a node does work proportional to that node's height, so the total work is S(h).
S(0) = 0 (a single node has height 0)
S(1) = 1 (one root at height 1, two leaves at height 0)
S(h) = 2·S(h-1) + 1 for the general recurrence
Solving the recurrence yields S(h) = 2^(h+1) - h - 2.
Since h ≤ lg(n), we get S(h) ≤ 2n - lg(n) - 2, which is O(n).
The key intuition: most nodes live near the bottom of the tree, and heapifyDown on bottom nodes does very little work (they have small heights). This is the opposite of heapifyUp, where bottom nodes do the most work.
Build a max-heap from the input array using heapifyDown. (O(n))
Swap the root (maximum element) with the last element in the heap.
Reduce the heap size by one, then heapifyDown on the new root. (O(log n))
Repeat steps 2 and 3 until the heap is empty.
Running time: O(n) for buildHeap + O(n log n) for n extractions = O(n log n) overall.
Heap sort matters because it is in-place (no extra array needed beyond a constant amount of memory) and guarantees O(n log n) worst-case, unlike quicksort which can degrade to O(n²).
Left child index: 2i
Right child index: 2i + 1
Parent index: i / 2 (integer division)
Height of a complete binary tree with n nodes: floor(log₂ n)
S(h) = 2^(h+1) - h - 2 (sum of all node heights in a complete tree of height h)
buildHeap (heapifyDown) total work: O(n)
Heap sort overall: O(n log n)
Priority queues built on heaps power Dijkstra's shortest-path algorithm and Prim's minimum spanning tree algorithm, both of which repeatedly need the smallest-weight edge or shortest tentative distance. Operating systems use heaps to schedule processes by priority, and heaps also appear in median-maintenance algorithms for streaming data.
Students often assume buildHeap with heapifyDown is O(n log n) because "there are n nodes and each might travel log n levels." The proof shows that most nodes are near the bottom and travel very little, so the total is O(n).
A common mistake is confusing a min-heap with a sorted array. In a min-heap, the root is the smallest element, but sibling nodes have no guaranteed order relative to each other. [_, 4, 5, 6, 15, 9, 7, 20] is a valid min-heap even though 5 < 6 at the same level.
Students sometimes forget that the heap array typically uses 1-based indexing (index 0 is unused). Using 0-based indexing changes the child/parent formulas to 2i+1, 2i+2, and (i-1)/2.
Heap sort uses a max-heap (not a min-heap) when sorting in ascending order in place, because you repeatedly move the largest remaining element to the end.
⚠️ Know all three buildHeap strategies and their running times. The O(n) proof for heapifyDown buildHeap is a classic exam question.
⚠️ Be ready to trace insert and removeMin operations on a given heap, showing each swap step by step.
⚠️ Understand why heap sort is O(n log n) and how it compares to quicksort and mergesort (in-place like quicksort, worst-case guaranteed like mergesort).
⚠️ Array index arithmetic (parent, left child, right child) is easy to get wrong under pressure. Practise it.
True or False: In a min-heap, the second-smallest element must be a child of the root.
True or False: buildHeap using heapifyDown runs in O(n log n) time.
Fill in the blank: For a node at index i in a 1-based heap array, its left child is at index ______.
True or False: Heap sort requires O(n) extra memory.
True or False: A sorted array in ascending order is a valid min-heap.
Answers: 1. True. 2. False (it is O(n)). 3. 2i. 4. False (it is in-place, O(1) extra). 5. True.
Q: You insert the value 3 into the min-heap [_, 4, 5, 6, 15, 9, 7, 20]. Show the resulting array after heapifyUp completes.
A: 3 is placed at index 8 (child of node at index 4, which is 15). 3 < 15, so swap: [, 4, 5, 6, 3, 9, 7, 20, 15]. 3 < 5, so swap: [, 4, 3, 6, 5, 9, 7, 20, 15]. 3 < 4, so swap: [_, 3, 4, 6, 5, 9, 7, 20, 15].
Q: What is the running time of building a heap using repeated heapifyUp, and why is it different from using repeated heapifyDown?
A: HeapifyUp buildHeap is O(n log n). Each element inserted may bubble up to the root, and the majority of elements are inserted when the tree is tall, so many elements travel close to log n levels. HeapifyDown buildHeap is O(n) because it starts from the bottom, where most nodes are, and those bottom nodes only travel a short distance.
Q: Explain why heap sort uses a max-heap rather than a min-heap when sorting an array in ascending order in place.
A: With a max-heap, the largest element is at the root. You swap it to the last position, shrink the heap by one, and heapifyDown. This places the largest elements at the end of the array in sorted order, working backwards. A min-heap would give you the smallest first at the front, but then the remaining elements would overwrite each other unless you used extra storage.
Q: Given the array [B, U, I, L, D, H, E, A, P, N, O, W], what does the heap look like after buildHeap with heapifyDown?
A: The result is [A, B, D, E, H, I, L, N, O, P, U, W] (alphabetical order or close to it, depending on specific swap paths). The root is A, the smallest letter.
Heaps connect directly to priority queues, which are used in Dijkstra's algorithm and Prim's algorithm (graph topics likely covered later in CS 225). The buildHeap proof is also a good exercise in recurrence relations, linking back to the algorithm analysis techniques from earlier in the course. Heap sort connects to the broader sorting landscape: it fills the gap as an in-place, O(n log n) worst-case sort.
heap, min-heap, max-heap, binary heap, priority queue, heapify, heapifyUp, heapifyDown, percolate up, percolate down, sift up, sift down, bubble up, bubble down, buildHeap, Floyd's algorithm, heap sort, heapsort, array-based tree, complete binary tree, CS 225, UIUC data structures, priority queue implementation