Heap / Priority Queue

Overview

A heap is the right data structure whenever you need:

• Top-K anything: maintain a size-K heap. The heap gives $O(n log K)$ instead of $O(n log n)$ sorting.
• Streaming order statistics: kth smallest/largest, running median, sliding-window extremes.
• Scheduling with dynamic priorities: reorganize, task scheduling, meeting rooms.
• Greedy selection: always take the best (cheapest, earliest, largest) element, then update.

Python: heapq is a min-heap on a list. Negate values for max-heap. Heaps don’t support efficient arbitrary key lookup, pair with a hash map for “delete or update by key” (see Twitter).

Problems

1. 703. Kth Largest Element in a Stream (Easy)
2. 1046. Last Stone Weight (Easy)
3. 973. K Closest Points to Origin (Medium)
4. 215. Kth Largest Element in an Array (Medium)
5. 621. Task Scheduler (Medium)
6. 355. Design Twitter (Medium)
7. 295. Find Median from Data Stream (Hard)

Key patterns unlocked here

• Size-K min-heap for online top-K: 703.
• Greedy selection with max-heap: 1046.
• Size-K heap by distance: 973.
• Quickselect vs. heap: 215 (classic time vs. space trade-off).
• Greedy scheduling with a counter and a max-heap: 621.
• Heap merge across per-user feeds: 355.
• Two heaps balancing a median: 295 (canonical).