Why This Matters
Learners often say "heap" when they mean "priority queue." The difference matters because one is the contract and the other is one way to satisfy it.
Decision Rule
Say priority queue when describing the operation you need: insert an item with priority and repeatedly remove the best item. Say heap when describing the array-based tree structure used to implement those operations.
Comparison Table
| Concept | Priority queue | Heap |
|---|---|---|
| Type | abstract data type | concrete data structure |
| Core operation | get min or max by priority | maintain heap invariant |
| Common implementation | binary heap, pairing heap, Fibonacci heap | binary heap in arrays |
| Python interface | heapq functions approximate min-priority queue behavior | heapq stores heap in a list |
| Used by | Dijkstra, A*, top-k, scheduling | the implementation behind many priority queues |
Worked Example
Dijkstra's algorithm needs a priority queue because it asks for the unsettled vertex with smallest current distance. In Python, heapq implements that priority queue with a min-heap list of (distance, vertex) pairs.
The algorithm cares about the priority queue behavior. The code cares about the heap invariant.
Common Mistakes
| Mistake | Correction |
|---|---|
| Calling every priority queue a binary heap. | Binary heap is common, not the only implementation. |
Expecting Python heapq to support decrease-key directly. | Most Python Dijkstra code pushes a new pair and skips stale entries. |
| Forgetting tuple tie behavior in Python. | If priorities tie, Python compares later tuple fields. Add a counter if needed. |
Diagnostic Questions
| Question | Answer signal |
|---|---|
| Which one is the abstraction? | Priority queue. |
| Which one has parent-child index relationships? | Binary heap. |
| Why does Dijkstra use one? | It needs efficient extraction of the smallest tentative distance. |
Exercises
- Beginner: Push
(3, "A"),(1, "B"),(2, "C")into a min-heap and list pop order. - Beginner: Explain why a sorted list can implement a priority queue but may be slower for insertion.
- Beginner: Name two algorithms that use priority queues.
- Intermediate: Implement top-k largest elements using a min-heap of size
k. - Intermediate: Implement Dijkstra with lazy stale-entry skipping.
- Challenge: Compare binary heap and Fibonacci heap operation bounds at a high level.
References
- MIT OpenCourseWare. 6.006 Introduction to Algorithms, Spring 2020: https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/
- MIT OpenCourseWare. 6.006 Sorting and heap materials, Spring 2020: https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/