aloalgoPriority Queue Patterns: Top-K and Beyond
When you need efficient access to the minimum or maximum element, a heap (priority queue) is your go-to data structure. While sorting gives you all elements in order at O(n log n), a heap lets you efficiently maintain just the elements you care about. This guide covers the essential heap patterns that appear frequently in coding interviews.Heap Basics
A heap is a complete binary tree where each parent is smaller (min-heap) or larger (max-heap) than its children. Python's heapq module provides a min-heap implementation.When to Use a Heap
Reach for a heap when you see these patterns:- Find the K largest/smallest elements
- Find the Kth largest/smallest element
- Continuously track min/max as elements arrive
- Merge multiple sorted sequences
- Find median in a stream
- Schedule tasks by priority
- Shortest path algorithms (Dijkstra's)
Pattern 1: Top-K Elements
The most common heap pattern. To find the K largest elements, use a min-heap of size K. This seems counterintuitive, but the min-heap efficiently keeps track of the K largest by discarding smaller elements.K Largest Elements
Kth Largest Element
Pattern 2: Top-K Frequent Elements
A variation where we first count frequencies, then find the top K by frequency.Top-K Frequent Words
Pattern 3: Merge K Sorted Lists
When merging K sorted sequences, a heap efficiently tracks the smallest element across all sequences.Merge K Sorted Linked Lists
Pattern 4: Two Heaps for Median
To find the median in a stream, use two heaps: a max-heap for the smaller half and a min-heap for the larger half. The median is at the top of one or both heaps.Pattern 5: Meeting Rooms / Scheduling
Heap helps track resource allocation over time, like finding minimum meeting rooms needed.Task Scheduler
Pattern 6: Dijkstra's Shortest Path
The heap is essential for Dijkstra's algorithm, efficiently selecting the next closest unvisited node.Network Delay Time
Pattern 7: Reorganize / Rearrange
Use a max-heap to greedily place the most frequent element while maintaining constraints.Pattern 8: Sliding Window Maximum
While often solved with a deque, a heap approach works too. Use lazy deletion to handle elements leaving the window.Complexity Summary
Common Mistakes to Avoid
1. **Forgetting Python's heapq is min-heap only**: Negate values for max-heap behavior.2. **Comparing non-comparable objects**: When pushing tuples, ensure all elements can be compared (use index as tiebreaker).3. **Wrong heap type for Top-K**: Use min-heap for K largest, max-heap for K smallest.4. **Not handling empty heap**: Always check before peeking or popping.5. **Using heap when sorting suffices**: If you need all elements sorted, just sort. Heap shines when K is small relative to n.Practice Problems
Try these problems to solidify your understanding:Medium:Hard:
Was this helpful?
Company
Practice
© 2026 aloalgo. All rights reserved.