Pattern 14 of 22
Heap / Priority Queue Pattern: Template + 163 LeetCode Problems
Keep only the best k elements, or always pull the smallest, in log time.
- Easy
- 13
- Medium
- 87
- Hard
- 63
What the heap / priority queue pattern is
A heap gives you the smallest element in constant time and maintains that promise through inserts and removals in logarithmic time, without ever fully sorting anything — which is the whole saving. For top-k questions, keep a min-heap capped at size k: push every element, pop whenever the heap grows past k, and the smallest survivor is the kth largest. That is O(n log k) against O(n log n) for a sort, and it works on a stream whose length you do not know. Python's heapq is min-only, so a max-heap is built by pushing negated values, and tuples are compared element by element — which is how you order by a key while carrying a payload, and also how you accidentally crash when the payload is a type that cannot be compared and two keys tie. The two-heap arrangement is worth memorising separately: a max-heap of the lower half against a min-heap of the upper half, rebalanced so their sizes differ by at most one, keeps the median at the tops.
When to use it
- You need the k largest, k smallest, or k closest — and k is much smaller than n.
- Elements arrive as a stream and the answer must stay current without re-sorting.
- A scheduling or simulation loop always processes the currently cheapest or earliest item.
- Dijkstra's algorithm, or any BFS where edges carry weights.
- A running median is required, which is the two-heap arrangement.
The heap / priority queue template in Python
The shape, not a solution to any one problem. Adapt the condition and the summary being maintained; the skeleton stays the same across the 163 problems listed below.
import heapq
def k_largest(nums, k):
heap = [] # min-heap holding the k best seen so far
for value in nums:
heapq.heappush(heap, value)
if len(heap) > k:
heapq.heappop(heap) # evict the smallest, keeping the top k
return sorted(heap, reverse=True) # heap[0] alone is the kth largestComplexity characteristics
- Time
- O(log n) per push or pop; O(n log k) for top-k
- Auxiliary space
- O(n), or O(k) for top-k
A heap is a complete binary tree, so sifting up or down touches one node per level and costs log n. Keeping a capped heap of size k answers top-k in O(n log k) against O(n log n) for a full sort — a real saving when k is small, and the only option at all when the input is a stream of unknown length. Building a heap from an array with heapify is O(n) rather than O(n log n), which is worth knowing when the whole input is available up front.
Eyes only
Meet the heap / priority queue problem you did not practise.
In the live round, Stealth Interview reads the problem off your screen, returns a working solution with a step-by-step explanation and its time and space complexity, and transcribes what the interviewer says. It's a desktop app for macOS and Windows, invisible to screen sharing.
All 163 heap / priority queue LeetCode problems
Every problem in the library the heap / priority queue pattern applies to, grouped by LeetCode's own difficulty rating. 138 of the 163 carry a complete Python solution with a worked example and complexity analysis; the rest are listed for completeness, with the LeetCode Premium ones marked.
Related LeetCode topics
Easy (13)
Medium (87)
Hard (63)
Heap / Priority Queue pattern FAQ
What is the heap / priority queue pattern?
A heap gives you the smallest element in constant time and maintains that promise through inserts and removals in logarithmic time, without ever fully sorting anything — which is the whole saving.
How many LeetCode problems use the heap / priority queue pattern?
This page lists 163 LeetCode problems that the heap / priority queue pattern applies to: 13 Easy, 87 Medium and 63 Hard. 138 of them carry a complete Python solution with complexity analysis.
What is the time complexity of the heap / priority queue pattern?
O(log n) per push or pop; O(n log k) for top-k time and O(n), or O(k) for top-k space. A heap is a complete binary tree, so sifting up or down touches one node per level and costs log n. Keeping a capped heap of size k answers top-k in O(n log k) against O(n log n) for a full sort — a real saving when k is small, and the only option at all when the input is a stream of unknown length. Building a heap from an array with heapify is O(n) rather than O(n log n), which is worth knowing when the whole input is available up front.
When should I use the heap / priority queue pattern in an interview?
You need the k largest, k smallest, or k closest — and k is much smaller than n. Elements arrive as a stream and the answer must stay current without re-sorting.
Which heap / priority queue problem should I start with?
LeetCode 506. Relative Ranks is the lowest-numbered Easy problem on this page, which makes it the usual starting point: the technique is visible without the problem's own complications getting in the way.
What patterns are related to heap / priority queue?
Sorting, Greedy, Breadth-First Search, Binary Search. Problems frequently sit in more than one of these, and the overlap is where the interesting follow-up questions come from.
More ways in: all 22 patterns, the curated study lists, or the full problem list.