aloalgoHeaps Summary
A quick reference for heap techniques and problems to practice. A heap is a specialized tree-based data structure that provides efficient access to the minimum or maximum element. It is the standard implementation behind priority queues, which are used extensively in algorithms like Dijkstra's shortest path, task scheduling, and streaming data analysis.In Python, the heapq module provides a min-heap implementation. For a max-heap, the common trick is to negate values before inserting and negate again when extracting. Understanding when a heap is the right tool and which type (min or max) to use is essential for solving problems that involve repeatedly accessing extreme values from a dynamic collection of elements.Key Concepts
The table below shows the time complexity of core heap operations. Notice that peeking at the minimum or maximum is constant time, while insertions and extractions are logarithmic. The heapify operation is notably O(n), not O(n log n), due to the way elements are sifted down from the bottom of the tree.| Operation | Time Complexity |
|---|---|
| Insert (push) | O(log n) |
| Extract min/max (pop) | O(log n) |
| Peek min/max | O(1) |
| Heapify array | O(n) |
Common Patterns
Most heap problems in interviews follow one of a few recognizable patterns. Learning to identify these patterns from the problem description is the key to solving heap problems quickly.- Top K Elements: Use min heap of size K for top K largest, max heap for top K smallest
- Kth Largest/Smallest: Maintain heap of size K, root is the answer
- Merge K Sorted: Push first element of each list, pop min and push next
- Running Median: Use two heaps (max heap for lower half, min heap for upper half)
- Dijkstra's Algorithm: Min heap for shortest path
Chapters
- Introduction to Heaps - Heap properties and structure
- Heap Implementation & Library - Using heapq in Python
- Min Heap vs Max Heap - When to use which
- Heap Patterns and Applications - Top K, merge, scheduling
Practice Problems
Easy
Medium
Hard
Was this helpful?
Company
Practice
© 2026 aloalgo. All rights reserved.