This cheat sheet covers heaps and priority queues, two important tools for organizing data by priority instead of by insertion order. Students need this reference because heaps appear in sorting, scheduling, graph algorithms, simulations, and many coding interviews. It summarizes how heaps are stored in arrays, how priority queue operations work, and why the time costs are efficient.
It is designed for quick review while solving programming problems or studying data structures.
A heap is a complete binary tree that follows either the min-heap rule or the max-heap rule. In an array-based heap, the parent and child positions are found using simple index formulas such as left = 2i + 1 and right = 2i + 2. Priority queues use heaps to support fast access to the highest-priority or lowest-priority item.
The most important operations are peek, insert, extract, sift up, sift down, and heapify.
Key Facts
- In a min-heap, every parent value is less than or equal to its children, so parent <= child.
- In a max-heap, every parent value is greater than or equal to its children, so parent >= child.
- For a 0-indexed heap array, the left child of index i is at 2i + 1 and the right child is at 2i + 2.
- For a 0-indexed heap array, the parent of index i is at floor((i - 1) / 2).
- The height of a heap with n elements is floor(log2 n), so insert and extract usually take O(log n) time.
- Peek returns the root element without removing it, so peek takes O(1) time.
- Heapify builds a valid heap from an unordered array in O(n) time when done bottom-up.
- Heaps do not keep all elements sorted, but they guarantee that the root has the highest priority according to the heap rule.
Vocabulary
- Heap
- A tree-based data structure that is complete and follows a parent-child ordering rule.
- Priority Queue
- An abstract data type where each item has a priority and the highest-priority item is removed first.
- Min-Heap
- A heap where the smallest value is at the root because each parent is less than or equal to its children.
- Max-Heap
- A heap where the largest value is at the root because each parent is greater than or equal to its children.
- Sift Up
- The process of moving a newly inserted element upward until the heap property is restored.
- Sift Down
- The process of moving a root element downward after removal or replacement until the heap property is restored.
Common Mistakes to Avoid
- Using 1-indexed formulas on a 0-indexed array is wrong because it gives incorrect child and parent positions. For 0-indexing, use left = 2i + 1, right = 2i + 2, and parent = floor((i - 1) / 2).
- Assuming a heap array is fully sorted is wrong because a heap only guarantees the parent-child priority rule. Siblings and distant nodes may appear in many valid orders.
- Removing the root without replacing it with the last element is wrong because the complete tree shape would be broken. Move the last element to the root, remove the last slot, then sift down.
- Forgetting to compare with the correct child during sift down is wrong because the heap property may remain broken. In a min-heap, swap with the smaller child, and in a max-heap, swap with the larger child.
- Claiming heapify is always O(n log n) is wrong for the bottom-up heap construction algorithm. Bottom-up heapify runs in O(n) because most nodes are near the bottom and move only a short distance.
Practice Questions
- 1 For a 0-indexed heap array, what are the left child, right child, and parent indices for i = 6?
- 2 Given the min-heap array [3, 5, 8, 9, 6, 12, 10], what value is returned by peek, and what value must be removed first by extract-min?
- 3 Insert 4 into the min-heap array [5, 7, 9, 12, 10, 15]. Show the array after each needed sift-up swap.
- 4 Why is a heap useful for a priority queue even though it does not store every element in sorted order?