Heap / Priority Queue
The Heap / Priority Queue Pattern
A heap keeps the smallest or largest element instantly reachable while allowing insertions and removals in logarithmic time. Keeping a heap of size k gives you the top k of a stream without ever sorting the whole input.
Interactive problems
Free to open
How do you recognise a heap / priority queue problem?
The question says "top k", "k largest", "k closest", "median of a stream", or requires repeatedly taking the current minimum — which is what makes it the engine inside Dijkstra and k-way merges.
What is the time complexity of the heap / priority queue pattern?
O(n log k) for a top-k pass against O(n log n) for a full sort. Peeking is O(1); push and pop are O(log n).
Heap / Priority Queue practice problems
Each problem pairs a worked explanation with an interactive visualizer you step through yourself, plus the implementation in JavaScript, Python, Java and C++.
Heap / Priority Queue problems by difficulty and complexity
The difficulty, running time and extra space of every heap / priority queue solution on this page, as each lesson derives them.
| Lesson | Difficulty | Best | Average | Worst | Space |
|---|---|---|---|---|---|
| Heap Overview | Easy | Ω(1) | Θ(log n) | O(log n) | O(n) |
| Kth Largest Element in an Array | Medium | Ω(n) | Θ(n log k) | O(n log k) | O(k) |
| K Closest Points to Origin | Medium | Ω(n) | Θ(n log k) | O(n log k) | O(k) |
| Find K Closest Elements | Medium | Ω(n) | Θ(n) | O(n) | O(k) |
| Merge K Sorted Lists | Hard | Ω(N) | Θ(N log k) | O(N log k) | O(k) |
| Find Median from Data Stream | Hard | Ω(log n) | Θ(log n) | O(log n) | O(n) |
Related patterns and concepts
The underlying technique is covered from first principles in the heap / priority queue lesson in the DSA visualizer curriculum. Heap / Priority Queue is one of the 17 coding interview patterns, and its problems also appear in the DSA 75 interview sprint.
Every other coding interview pattern
Depth-First Search · 25 lessons
- Introduction to DFSFree
- DFS FundamentalsFree
- Return Values in DFS
- Invert Binary Tree
- Maximum Depth of Binary Tree
- Path Sum
- Passing Values Down (State)
- Validate Binary Search Tree
- Kth Smallest Element in a BST
- Construct Binary Tree from Preorder and Inorder Traversal
- Binary Tree Tilt
- Diameter of Binary Tree
- Lowest Common Ancestor of a Binary Tree
- Path Sum II
- Longest Univalue Path
- Graphs Overview
- Graph Representation: Adjacency List
- Clone Graph
- Graph Valid Tree
- Matrices as Graphs
- Flood Fill
- Types of DFS (Tree Traversals)
- Number of Islands
- Surrounded Regions
- Pacific Atlantic Water FlowFree