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?
Understanding Heap & Priority Queue Reference
A heap gets its speed by making a limited promise about order. It does not compare every item with every other item. It only checks the relationships needed to keep the most urgent item at the top.
Values in different branches may seem out of order, and that is normal. For example, a smaller value can appear below a larger value in a min heap if they are not parent and child.
This is why a heap is useful when a program repeatedly needs the next best item, rather than a fully sorted collection. The compact tree shape matters because it keeps every path from the top short.
When a new item enters a heap, it is first placed in the next open array position. This preserves the compact shape. Its priority may be wrong relative to its parent, so the item moves upward one level at a time.
Each swap fixes one local problem. Removing the top item works in the opposite direction. The last array item moves to the root, which avoids leaving a gap.
It may then move downward. At each level, it swaps with the child that should be above it.
In a min heap, that is normally the smaller child. Choosing the wrong child can leave a broken heap even if the first swap looked correct.
Building a heap from existing data has an important idea behind it. The last part of the array contains leaves, and leaves already satisfy the heap rule because they have no children. Work backward from the last parent toward the root.
Each parent is pushed down until its small subtree is correct. Small subtrees are fixed first, so larger subtrees can rely on them. This bottom up method is faster than inserting every value separately.
Most nodes are close to the bottom and can move only a short distance. Only a few nodes near the root can move many levels. That uneven amount of work makes total heapify time proportional to the number of items.
Students often confuse a priority queue with a sorted list. A priority queue gives fast access to one extreme item, but finding an arbitrary value can still require checking many positions. Removing a specific item is not automatically fast unless the program stores its index somewhere.
In graph algorithms such as Dijkstra's algorithm, a path estimate may improve after an item was inserted. Some libraries support priority updates. Others use a simpler method that inserts a new entry and ignores outdated entries when they reach the top.
In task schedulers, equal priorities need careful treatment. A normal heap does not guarantee that equal items leave in their original arrival order.
Add a sequence number when fair ordering matters. When tracing code, always track the array after every swap and check only parent child relationships.