Heap Priority Queue

A heap is useful when the next best candidate changes as you process data. It does not fully sort the input; it keeps just enough order to extract the minimum, maximum, or current top-k efficiently.

Quick Identifier

• Topic: heap-priority-queue
• Pattern: Top-k min-heap, max-heap simulation, two heaps, or scheduling heap.
• Core Question: Do we repeatedly need the best available candidate without sorting everything?

Quick Sights

• Typical Time Complexity: O(n log k) for top-k, O(n log n) for full heap scheduling, O(log n) per stream update.
• Typical Space Complexity: O(k) or O(n) depending on how many candidates remain live.
• Core Mechanism: Push candidates into a heap ordered by the decision priority; pop stale or completed candidates when they no longer belong.

Diagram

Recognition Cues

• Kth largest/smallest, closest points, top-k frequent, or median stream.
• Scheduling by earliest time, shortest processing time, or max profit.
• Merge k sorted streams/lists/ranges.

Problem List

Start with 703. Kth Largest in Stream, 215. Kth Largest Element, 973. K Closest Points, 295. Find Median from Data Stream, and 621. Task Scheduler.