Heap / Priority Queue
A heap keeps the smallest (or largest) element instantly available, giving O(log n) inserts and pops — ideal for "top-k" and streaming-order problems.
Key ideas
- —A binary heap gives O(1) peek at the extreme and O(log n) push/pop.
- —For "k largest", keep a min-heap of size k and evict the smallest.
- —Two balanced heaps (a max-heap and a min-heap) maintain a running median.
Top-k without full sorting
To find the k largest elements you do not need to sort all n. Maintain a min-heap capped at size k: push each element, and if the heap grows past k, pop the smallest. What remains is the top k, achieved in O(n log k) instead of O(n log n). Kth Largest Element and Top K Frequent Elements both use this pattern.
Two heaps for a median
To track the median of a stream, keep a max-heap of the lower half and a min-heap of the upper half, rebalancing so their sizes differ by at most one. The median is then a heap top or the average of the two tops, computed in O(1) after each O(log n) insertion. Merging k sorted lists uses a single heap of list heads the same way.
Practice this
Sources
- Heap (data structure)Wikipedia
- heapq — heap queue algorithmPython docs