A heap is a container with exactly one promise: you can always see and remove the smallest item in it, cheaply, no matter how many items are inside. Adding costs O(log n); removing the smallest costs O(log n); looking at the smallest costs O(1). Nothing else is fast — you cannot ask a heap for the second-smallest, cannot search it, cannot index it. It is deliberately a narrow tool.

That narrowness is the point. Reach for a heap when the question has this shape: "I keep receiving items, and at every moment I need the best-so-far, but I do not need the whole thing sorted." Sorting gives you far more than you asked for and charges O(n log n) for it. A heap charges only for what you use.

The Admission Threshold Invariant (Top-K Inversion)

The counter-intuitive move that makes top-K problems work is the Admission Threshold Invariant:

To keep the k largest items, maintain a min-heap of size k.
The root of a min-heap (heap[0]) is the smallest of the top k survivors seen so far. It represents the minimum qualification bar: any newly arriving element only earns a spot in the top k if it strictly beats the root (x > heap[0]). If it does, evicting the root removes the weakest candidate, and pushing x restores the threshold in $O(\log k)$.
Conversely, to keep the k smallest items, maintain a max-heap of size k where the root acts as the ceiling threshold.

🔬 Variable Anatomy: The 7 Variables Every Heap / Priority Queue Uses

To connect abstract priority queue mechanics with concrete Python syntax, here is the universal code anatomy showing what every variable does:

import heapq
import itertools
from collections import Counter
 
def heapMasterTemplate(
    items: list[int],
    k: int
) -> tuple[list[int], float]:
    # =========================================================================
    # 1. THE STORAGE & HEAP BUFFERS
    # =========================================================================
    heap = []                    # 🧵 Primary Bounded Heap (stores (priority_key, payload))
    small = []                   # 📉 Max-Heap (stores negated values for lower half in median)
    large = []                   # 📈 Min-Heap (stores positive values for upper half in median)
    counter = itertools.count()  # 🔢 Monotonic Unique Tie-Breaker (prevents payload comparison errors)
 
    # =========================================================================
    # 2. BOUNDED TOP-K SURVIVOR SELECTION PIPELINE (O(N log K))
    # =========================================================================
    # Count frequencies: items -> (count, val)
    freq_map = Counter(items)
    
    for val, freq in freq_map.items():
        # Push (priority_key, tie_breaker, payload) tuple
        heapq.heappush(heap, (freq, next(counter), val))
        
        # ⚠️ CRITICAL: Evict the weakest survivor when size exceeds k
        if len(heap) > k:
            heapq.heappop(heap)  # Discards the minimum frequency among current Top-K
 
    top_k_survivors = [val for _freq, _idx, val in heap]
 
    # =========================================================================
    # 3. DUAL-HEAP STREAMING BALANCING (O(log N) insert, O(1) median)
    # =========================================================================
    for num in items:
        # Step 1: Always push negated to small (max-heap)
        heapq.heappush(small, -num)
        # Step 2: Route max of small to large (min-heap) to enforce small <= large
        heapq.heappush(large, -heapq.heappop(small))
        # Step 3: Rebalance sizes so len(small) >= len(large)
        if len(large) > len(small):
            heapq.heappush(small, -heapq.heappop(large))
 
    # Calculate O(1) median
    median = float(-small[0]) if len(small) > len(large) else (-small[0] + large[0]) / 2.0
 
    return top_k_survivors, median
 

Variable Role Reference:

🧠 The Heap is NOT a Sorted Array: heap[0] is guaranteed minimal in $O(1)$, but iterating heap[1..] is NOT in sorted order. If sorted output is required, sort the final $K$ elements in $O(K \log K)$.

🌟 The 3 Dimensions of Heap / Priority Queue & The "Weakest Survivor" Principle

Every Heap / Priority Queue algorithm is defined by 3 Key Dimensions:

┌─────────────────────────────────────────────────────────────────────────────┐
│                    THE 3 DIMENSIONS OF HEAP & PRIORITY QUEUES               │
├───────────────────┬───────────────────────────────────┬─────────────────────┤
│ Dimension         │ Mechanism in Code                 │ Question It Answers │
├───────────────────┼───────────────────────────────────┼─────────────────────┤
│ 1. CAPACITY BOUND │ `len(heap) > k: heappop()`        │ "Is the working set │
│    (Memory Cap)   │ Bounded size-K vs Unbounded size-N│ memory bounded?"    │
├───────────────────┼───────────────────────────────────┼─────────────────────┤
│ 2. EXTREMUM POLAR │ Min-Heap (`heapq`) vs             │ "Are we evicting the│
│    (Inversion)    │ Max-Heap (Negated key `-val`)     │ minimum or maximum?"│
├───────────────────┼───────────────────────────────────┼─────────────────────┤
│ 3. STREAM DYNAMICS│ Single Filter, Dual-Heap Median,  │ "How do incoming    │
│    (Multi-Heap)   │ or K-Way Merge Pointer Array      │ streams interact?"  │
└───────────────────┴───────────────────────────────────┴─────────────────────┘
 

How this plays out in actual problems:

🟢 Scenario A: Bounded Top-K Selection (Min-Heap of Size K)

• When finding the $K$ largest elements from $N$ items, sorting the entire array costs $O(N \log N)$ time and $O(N)$ space.
• The Rule: Maintain a min-heap of capacity $K$. For each item, heappush(heap, item). If len(heap) > k, heappop(heap) evicts the smallest item.
• The Result: Time collapses to $O(N \log K)$ and auxiliary space stays fixed at $O(K)$.

🔵 Scenario B: Two-Heap Streaming Median (Small Max-Heap + Large Min-Heap)

• In a continuous stream of numbers, sorting on every query costs $O(N^2 \log N)$.
• The Rule: Partition numbers into two halves: small (max-heap) and large (min-heap). Route new numbers through small into large, then rebalance sizes so len(small) >= len(large).
• The Result: Insertion takes $O(\log N)$ and median queries take instant $O(1)$ time!

🟣 Scenario C: K-Way Sorted Stream Merging (Tournament Frontier)

• Given $K$ sorted linked lists, pairwise merging takes $O(N \cdot K)$ time.
• The Rule: Push the head node of each of the $K$ lists into a size-$K$ min-heap (node.val, list_idx, node). Pop the global minimum, advance its node.next, and push back into the heap.
• The Result: Merges all $N$ total elements in optimal $O(N \log K)$ time.

💡 The Ultimate Takeaway Decision Rule:
When analyzing an extremum or ordering problem, ask: "Do I need the whole dataset sorted, or only the extremums / dynamic balance?"

• If Top-K Largest ➔ Size-$K$ Min-Heap ($O(N \log K)$).
• If Running Median ➔ Dual Balanced Heaps (Max-Heap + Min-Heap in $O(1)$ query).
• If K Sorted Streams ➔ Size-$K$ Tournament Min-Heap ($O(N \log K)$).
• If Cooldown Reorganization ➔ Max-Heap with temporary holding cooldown buffer.

🎯 The 5 Essential Heap Paradigms & Archetypes

┌──────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐
│                                       THE 5 CORE HEAP ARCHETYPES                                                 │
├────────────────────────┬──────────────────────┬───────────────────────────────┬──────────────────────────────────┤
│ Archetype              │ State Management     │ Heap Inversion / Key Rule     │ Invariant / Eviction Rule        │
├────────────────────────┼──────────────────────┼───────────────────────────────┼──────────────────────────────────┤
│ 1. Bounded Top-K       │ Size-$K$ Min-Heap    │ Score key first in tuple:     │ If `len(heap) > k: heappop()`    │
│    (LC 347 / LC 215)   │ `heap = []`          │ `(count, idx, val)`           │ Root is cut-off threshold        │
├────────────────────────┼──────────────────────┼───────────────────────────────┼──────────────────────────────────┤
│ 2. Dual-Heap Median    │ `small` (Max-Heap) & │ Negate values for `small`:    │ Invariant: `0 <= len(small) -    │
│    (LC 295 / LC 480)   │ `large` (Min-Heap)   │ `heappush(small, -x)`         │ len(large) <= 1`; small <= large │
├────────────────────────┼──────────────────────┼───────────────────────────────┼──────────────────────────────────┤
│ 3. K-Way Merge         │ Size-$K$ Min-Heap of │ Current list head pointer:    │ Extract minimum, advance `next`, │
│    (LC 23 / LC 373)    │ list head nodes      │ `(node.val, list_i, node)`    │ replenish heap with new head     │
├────────────────────────┼──────────────────────┼───────────────────────────────┼──────────────────────────────────┤
│ 4. Greedy Reorganize   │ Max-Heap with        │ Negate frequency for max-heap:│ Pop highest frequency, place,    │
│    (LC 767 / LC 621)   │ Cooldown Buffer      │ `(-freq, char)`               │ hold in cooldown, re-push later  │
├────────────────────────┼──────────────────────┼───────────────────────────────┼──────────────────────────────────┤
│ 5. Regret Scheduling   │ Max-Heap of past     │ Durations in Max-Heap:        │ If `total_time > deadline`:      │
│    (LC 630 / LC 1642)  │ durations taken      │ `heappush(max_h, -duration)`  │ evict longest duration taken     │
└────────────────────────┴──────────────────────┴───────────────────────────────┴──────────────────────────────────┘
 

🏆 1. Bounded Min-Heap for Top-K Frequent Elements (LC 347 & 215)

• Mental Model: Count each value, then apply the Admission Threshold above to the counts: push (freq, num) and pop the root whenever the heap grows past $K$.
• Code: see the Top-K Heap card.

⚖️ 2. Dual-Heap Dynamic Running Median (LC 295)

• Mental Model: Divides the dynamic number line into two equal halves with a max-heap on the left and a min-heap on the right.
• Code: see the Two Heaps card.

🔀 3. K-Way Sorted Stream Merging (LC 23)

• Mental Model: A tournament bracket where $K$ list heads compete; the winner is added to the merged output and replaced by its successor.
• Code: see the K-Way Merge card.

🔄 4. Greedy Frequency Reorganization (LC 767)

• Mental Model: Greedily pick the most frequent character, place it, and hold it in a temporary variable until the next character is chosen to prevent adjacent duplicates.
• Code: see the Most Frequent First card.

⏱️ 5. Greedy Regret Scheduling (LC 630 — Course Schedule III)

• Mental Model: When deadlines are violated, regret past decisions by evicting the course with the longest duration to free up maximum remaining time.
• Code: see the Greedy with Regret card.

🌳 Evaluating Heap Topologies, State Management & Frontier Management

Understanding the performance and memory mechanics of binary heaps ensures reliable implementation:

1. Linear Heapify vs Repeated Heappush

• heapq.heapify(lst) runs in mathematically guaranteed $O(N)$ linear time using bottom-up sift-down.
• Repeatedly calling heappush $N$ times takes $O(N \log N)$ time. When the full array is available upfront, always use heapify().

2. Tuple Sorting & Tie-Breaking Invariants

• Python compares tuples element-by-element (tuple[0], then tuple[1]). Always place the numeric sort key first.
• Always include a monotonic counter (itertools.count()) as a middle field if payloads cannot be compared with <.

💡 Staff SWE Architectural Invariant:
A heap is an extremum filter, not a sorting algorithm. Use a bounded min-heap of size $K$ to compress memory from $O(N)$ to $O(K)$, and never inspect heap elements beyond heap[0] expecting sorted order.