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.

Think of it as lazy sorting: globally unsorted detail is allowed as long as the root (or comparator-chosen apex) always holds the Extreme element you care about (min heaps for “give me earliest deadline”; max heaps for profit). Many languages expose only one polarity—keep a consistent rule (Java PriorityQueue = min-first; heapq = min; negate values or invert comparisons for max).

Two-heaps tricks (streaming median): split “lower half → max heap” vs “upper half → min heap” so you can peek medians from tops only.

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.