7a:T518,import heapq from collections import defaultdict def dijkstra(graph: dict, start: str) -> dict: """ Dijkstra's shortest path algorithm using a min-heap. The min-heap stores (distance, vertex) pairs. Python's heapq is a min-heap by default, making this natural. Time Complexity: O((V + E) log V) Space Complexity: O(V) """ # distances[v] = shortest known distance from start to v distances = {start: 0} # Min-heap: (distance, vertex) # Smallest distance always at the root min_heap = [(0, start)] while min_heap: # Extract vertex with MINIMUM distance current_dist, current_vertex = heapq.heappop(min_heap) # Skip if we've already found a shorter path if current_dist > distances.get(current_vertex, float('inf')): continue # Explore neighbors for neighbor, weight in graph[current_vertex]: distance = current_dist + weight # If this path is shorter, record it if distance < distances.get(neighbor, float('inf')): distances[neighbor] = distance # Add to min-heap for future processing heapq.heappush(min_heap, (distance, neighbor)) return distances7b:T4f5,import heapq from typing import List def merge_k_sorted_lists(lists: List[List[int]]) -> List[int]: """ Merge K sorted lists into one sorted list using a min-heap. The min-heap maintains the smallest unprocessed element from each list. We always extract the global minimum, then push the next element from that list. Time Complexity: O(N log K) where N = total elements, K = number of lists Space Complexity: O(K) for the heap """ result = [] # Min-heap entries: (value, list_index, element_index) # This ensures we can track which list to pull from next min_heap = [] # Initialize heap with first element from each non-empty list for i, lst in enumerate(lists): if lst: # Only add non-empty lists heapq.heappush(min_heap, (lst[0], i, 0)) while min_heap: # Extract the globally smallest element value, list_idx, elem_idx = heapq.heappop(min_heap) result.append(value) # If the source list has more elements, add the next one if elem_idx + 1 < len(lists[list_idx]): next_value = lists[list_idx][elem_idx + 1] heapq.heappush(min_heap, (next_value, list_idx, elem_idx + 1)) return result7c:T8b1,import heapq from dataclasses import dataclass, field from typing import Any, Callable @dataclass(order=True) class Event: """ An event in a discrete event simulation. The @dataclass(order=True) decorator makes Events comparable by their fields in order. Since 'time' comes first, events are ordered by time. The 'action' field is excluded from comparison to avoid comparing functions. """ time: float action: Callable[[], None] = field(compare=False) data: Any = field(default=None, compare=False) class EventQueue: """ A min-heap-based event queue for discrete event simulation. Events are processed in strict chronological order, regardless of the order in which they were scheduled. """ def __init__(self): self._heap: list[Event] = [] self._current_time: float = 0.0 def schedule(self, time: float, action: Callable, data: Any = None) -> None: """Schedule an event to occur at the specified time.""" if time < self._current_time: raise ValueError("Cannot schedule events in the past") heapq.heappush(self._heap, Event(time, action, data)) def schedule_relative(self, delay: float, action: Callable, data: Any = None) -> None: """Schedule an event to occur after a delay from current time.""" self.schedule(self._current_time + delay, action, data) def process_next(self) -> bool: """ Process the next event (the one with smallest time). Returns True if an event was processed, False if queue is empty. """ if not self._heap: return False event = heapq.heappop(self._heap) self._current_time = event.time event.action() return True def run_until(self, end_time: float) -> None: """Process all events up to and including end_time.""" while self._heap and self._heap[0].time <= end_time: self.process_next() @property def current_time(self) -> float: return self._current_time @property def next_event_time(self) -> float | None: return self._heap[0].time if self._heap else None7d:T7fa,import heapq from typing import Iterator class TopKTracker: """ Efficiently track the K largest elements in a data stream. Uses a MIN-heap of size K. This is the correct choice because: - The root (minimum) is the threshold: if a new element exceeds it, the new element belongs in the top K. - When we add a new element to top K, we remove the old minimum. - At any time, the heap contains exactly the K largest seen elements. This is a classic example where min-heap solves a "maximum" problem! """ def __init__(self, k: int): if k <= 0: raise ValueError("k must be positive") self.k = k self._heap: list = [] def add(self, value: float) -> None: """ Process a new value from the stream. Time Complexity: O(log K) """ if len(self._heap) < self.k: # Heap not yet full: just add heapq.heappush(self._heap, value) elif value > self._heap[0]: # New value exceeds current K-th largest # Remove the old K-th largest, add the new value heapq.heapreplace(self._heap, value) # If value <= heap[0], it's not in top K, ignore it def get_top_k(self) -> list: """ Return the current top K elements (not necessarily sorted). Time Complexity: O(K log K) if you want them sorted """ return sorted(self._heap, reverse=True) def get_kth_largest(self) -> float | None: """ Return the K-th largest element seen so far. Time Complexity: O(1) """ if len(self._heap) < self.k: return None # Haven't seen K elements yet return self._heap[0] # Root of min-heap is the K-th largest # Example usage def process_stream(stream: Iterator[float], k: int) -> list: """Process an entire stream and return top K elements.""" tracker = TopKTracker(k) for value in stream: tracker.add(value) return tracker.get_top_k()7e:T81a,import heapq from dataclasses import dataclass, field from typing import Any from enum import IntEnum class Priority(IntEnum): """ Task priorities where LOWER values = HIGHER importance. This convention works naturally with min-heaps. """ CRITICAL = 0 HIGH = 1 NORMAL = 2 LOW = 3 BACKGROUND = 4 @dataclass(order=True) class Task: """ A schedulable task with priority and optional deadline. Tasks are ordered by: 1. Priority (lower = more urgent) 2. Deadline (earlier = more urgent) 3. Arrival time (FIFO for equal priority/deadline) """ priority: Priority deadline: float arrival_time: float task_id: str = field(compare=False) payload: Any = field(default=None, compare=False) class TaskScheduler: """ A priority-based task scheduler using a min-heap. The min-heap naturally surfaces the most urgent task: - Smallest priority value (CRITICAL < HIGH < NORMAL...) - Among equal priorities, earliest deadline - Among equal deadlines, first arrival (FIFO) """ def __init__(self): self._heap: list[Task] = [] self._task_count = 0 def submit(self, task_id: str, priority: Priority, deadline: float = float('inf'), payload: Any = None) -> None: """Submit a new task to the scheduler.""" task = Task( priority=priority, deadline=deadline, arrival_time=self._task_count, # Monotonic for FIFO task_id=task_id, payload=payload ) heapq.heappush(self._heap, task) self._task_count += 1 def get_next(self) -> Task | None: """Get the most urgent task (smallest priority value).""" if not self._heap: return None return heapq.heappop(self._heap) def peek(self) -> Task | None: """See the most urgent task without removing it.""" return self._heap[0] if self._heap else None def is_empty(self) -> bool: return len(self._heap) == 072:{"json":{"id":"seed_96a0c4c1cd198d2780a81776fff68b62","slug":"min-heap-vs-max-heap","category":"Data Structures & Algorithms","topic":"Heaps & Priority Queues","title":"Min-Heap vs Max-Heap","description":"Master the art of choosing between min-heaps and max-heaps. Learn when each variant excels, how to convert between them, and understand language-specific defaults across programming ecosystems.","difficulty":"INTERMEDIATE","estimatedMinutes":55,"pages":[{"id":"seed_bbbb7f707c6d8524d87a7ee6c3161180","title":"When to Use Min-Heap","order":0,"content":[{"id":"opening-hook","title":"The Art of Finding the Smallest","content":[{"data":{"content":"In the realm of data structures, few constructs offer the elegant efficiency of the heap. While heaps fundamentally solve the same problem—maintaining quick access to an extreme value—the choice between a **min-heap** and a **max-heap** profoundly shapes your algorithm's behavior, correctness, and intuition.\n\nThis page focuses on the **min-heap**: a complete binary tree where every parent node is smaller than or equal to its children. The smallest element perpetually resides at the root, accessible in O(1) time. But knowing the *definition* isn't enough—mastery requires understanding **when** and **why** to reach for this particular tool."},"type":"text"},{"data":{"icon":"Target","title":"What You Will Learn","content":"By the end of this page, you will develop deep intuition for min-heap use cases. You'll recognize problem patterns that scream 'min-heap!', understand the semantic meaning behind the choice, and see how production systems leverage min-heaps for critical functionality.","variant":"info"},"type":"callout"}]},{"id":"fundamental-insight","title":"The Fundamental Insight: What Does \"Minimum\" Really Mean?","content":[{"data":{"content":"Before diving into use cases, we must establish a foundational principle that guides all heap selection decisions:\n\n**A min-heap gives you efficient access to the element with the *smallest* priority value.**\n\nThis statement seems obvious, but its implications are subtle. The word \"priority\" here isn't merely the element's value—it's a **comparison key** that determines ordering. Understanding this distinction unlocks powerful problem-solving techniques."},"type":"text"},{"data":{"items":["**Min-heap surfaces the smallest key** — Whatever you use for comparison rises to the top if it's the minimum.","**Smallest can mean most important** — In many systems, lower numbers represent higher urgency (priority 1 > priority 5).","**Smallest can mean earliest** — Timestamps, deadlines, and scheduled times: the earliest event has the smallest time value.","**Smallest can mean cheapest** — Costs, distances, and weights: the shortest path comes from the smallest accumulated cost.","**Smallest can mean most constrained** — In optimization, the tightest bound or most limited option often drives the solution."],"title":{"icon":"Key","text":"The Priority Interpretation Principle","type":"icon","color":"primary","variant":"outline-circle"},"variant":"glass"},"type":"list"},{"data":{"content":"**The profound implication:**\n\nWhen you encounter a problem requiring access to the \"first,\" \"next,\" \"closest,\" \"cheapest,\" \"earliest,\" or \"most urgent\" element, you're often looking at a min-heap problem—even if the problem statement never mentions heaps.\n\nThe ability to recognize this pattern separates developers who struggle with priority problems from those who solve them elegantly."},"type":"text"},{"data":{"icon":"Lightbulb","title":"Mental Model","content":"Think of a min-heap as a \"next action queue\" — it always tells you what to process next when \"next\" means the smallest, earliest, or cheapest. The root is perpetually your answer to: \"What should I do now?\"","variant":"tip"},"type":"callout"}],"titleType":"number","titleNumber":1},{"id":"classic-patterns","title":"Classic Min-Heap Patterns in Algorithm Design","content":[{"data":{"content":"Certain algorithmic patterns have become synonymous with min-heap usage. These aren't arbitrary associations—they emerge from the fundamental nature of problems that require repeated extraction of the minimum element."},"type":"text"},{"data":{"items":["**Dijkstra's Algorithm** — The quintessential min-heap application. Each iteration extracts the vertex with the smallest tentative distance.","**Why it works** — Greedy selection of the minimum-distance vertex guarantees correctness for non-negative edge weights.","**Without min-heap** — Finding the minimum vertex would require O(V) scan per iteration, yielding O(V²) overall vs O((V+E) log V) with a min-heap.","**Semantic fit** — We want the \"closest\" unvisited vertex; \"closest\" means smallest distance; min-heap provides exactly this."],"title":{"icon":"Route","text":"Pattern 1: Shortest Path Algorithms","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"code":"$7a","fileName":"dijkstra_min_heap.py","language":"python"},"type":"code"},{"data":{"items":["**The problem** — Given K sorted lists/streams, produce a single sorted output.","**Why min-heap** — At any moment, we need the globally smallest element across K candidates. The min-heap maintains these K \"front\" elements.","**Efficiency gain** — Extract minimum in O(log K), process N total elements: O(N log K) vs O(N × K) for naive comparison.","**Real applications** — Merge sort's final merge, external sorting from multiple files, combining sorted database shards."],"title":{"icon":"GitMerge","text":"Pattern 2: Merge K Sorted Sequences","type":"icon","color":"secondary","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"code":"$7b","fileName":"merge_k_sorted.py","language":"python"},"type":"code"},{"data":{"items":["**The problem** — Find the subset of edges that connects all vertices with minimum total weight.","**Why min-heap** — At each step, we add the cheapest edge connecting the growing tree to an unvisited vertex.","**The insight** — \"Cheapest\" means smallest weight, making min-heap the natural choice.","**Correctness guarantee** — The greedy selection of minimum edges provably produces the optimal spanning tree."],"title":{"icon":"TreeDeciduous","text":"Pattern 3: Minimum Spanning Tree (Prim's Algorithm)","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"}],"titleType":"number","titleNumber":2},{"id":"event-driven-systems","title":"Min-Heaps in Event-Driven Systems","content":[{"data":{"content":"Perhaps no domain demonstrates min-heap utility more clearly than **event-driven systems**. Whenever a system must process events in chronological order—but events may be scheduled out of order—a min-heap becomes indispensable."},"type":"text"},{"data":{"icon":"Clock","title":"The Core Insight","content":"Time flows forward. The event that should happen next is the one with the smallest timestamp. A min-heap keyed by timestamp always has the \"next\" event at its root.","variant":"note"},"type":"callout"},{"data":{"items":["**Discrete Event Simulation** — Simulating traffic flow, network protocols, or queuing systems. Events are scheduled at specific times; the simulator processes them in order using a min-heap.","**Timer Management in Operating Systems** — The OS maintains a min-heap of pending timers. When a timer fires, it extracts the minimum; when a new timer is set, it inserts into the heap.","**Scheduled Task Execution** — Cron-like systems, job schedulers, and task queues. The next job to run is the one with the earliest scheduled time.","**Real-Time Systems** — Rate-monotonic scheduling and earliest-deadline-first (EDF) scheduling both use min-heaps keyed by deadline or period.","**Game Engine Event Loops** — Physics simulations, AI decision cycles, and animation keyframes—all scheduled and processed via time-ordered event queues."],"title":{"icon":"Timer","text":"Event-Driven Applications","type":"icon","color":"primary","variant":"outline-circle"},"variant":"glass"},"type":"list"},{"data":{"code":"$7c","fileName":"event_simulation.py","language":"python"},"type":"code"},{"data":{"content":"**Why the min-heap is essential here:**\n\nEvent-driven systems have a critical requirement: **events must be processed in time order, but they're often scheduled out of order**. An event at time T=100 might schedule follow-up events at T=105, T=110, and T=95. The system must still process T=95 next (if it hasn't passed).\n\nA sorted list would require O(n) insertion to maintain order. A min-heap provides O(log n) insertion and O(log n) extraction—exactly the operations event loops need."},"type":"text"}],"titleType":"number","titleNumber":3},{"id":"streaming-data","title":"Streaming Data and Running Minimums","content":[{"data":{"content":"In streaming scenarios, data arrives continuously and you must answer queries without storing everything. Min-heaps excel at several streaming patterns:"},"type":"text"},{"data":{"items":["**Counterintuitive insight** — To find the K *largest* elements, use a *min*-heap of size K.","**How it works** — Maintain a min-heap of the K largest elements seen so far. The root is the K-th largest (the *smallest* of the top K).","**When new element arrives** — If it's larger than the root, remove the root and insert the new element.","**Why min-heap** — The root (minimum) acts as a \"gatekeeper\": anything smaller than it doesn't belong in the top K.","**Space efficiency** — Only O(K) space regardless of total data volume—critical for processing billions of records."],"title":{"icon":"TrendingUp","text":"Streaming Pattern: Finding K Largest Elements","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"code":"$7d","fileName":"top_k_stream.py","language":"python"},"type":"code"},{"data":{"icon":"AlertCircle","title":"The Paradox Explained","content":"Using a min-heap for finding maximum elements seems backwards at first. The key insight: we're not directly finding the maximum—we're maintaining a \"club\" of the K largest, using the minimum as the entry barrier. Any new element must beat the current weakest member (the minimum of the top K) to join.","variant":"warning"},"type":"callout"},{"data":{"items":["**Running Median** — Use a max-heap for the lower half and a min-heap for the upper half. The min-heap's root is the smallest of the larger half.","**Sliding Window Minimum** — While a deque is often optimal, min-heaps with lazy deletion work for certain variants.","**Heavy Hitters / Frequent Items** — Space-saving algorithms use min-heaps to track the K most frequent items in a stream.","**Rate Limiting** — Track request timestamps in a min-heap; remove timestamps older than the window by extracting minimums."],"title":{"icon":"Activity","text":"Additional Streaming Applications","type":"icon","color":"secondary","variant":"outline-circle"},"variant":"glass"},"type":"list"}],"titleType":"number","titleNumber":4},{"id":"task-scheduling","title":"Task Scheduling with Priorities","content":[{"data":{"content":"Task scheduling is a domain where min-heaps appear constantly, but the mapping between \"priority\" and \"minimum\" requires careful thought."},"type":"text"},{"data":{"icon":"Info","title":"The Priority Inversion Convention","content":"In most systems, lower priority numbers mean higher importance (priority 1 is more urgent than priority 5). This convention makes min-heaps the natural choice: the most urgent task has the smallest priority value and rises to the root.","variant":"note"},"type":"callout"},{"data":{"items":["**Shortest Job First (SJF)** — CPU scheduling where the job with the smallest execution time runs next. Minimizes average waiting time.","**Earliest Deadline First (EDF)** — Real-time scheduling where the task with the earliest (smallest) deadline runs next.","**Huffman Coding** — Building optimal prefix codes by repeatedly combining the two nodes with smallest frequencies.","**A* Search** — Selecting the node with smallest f(n) = g(n) + h(n) for expansion.","**Bandwidth Allocation** — Fairness algorithms that serve the flow with the smallest \"virtual time\" next."],"title":{"icon":"ListChecks","text":"Scheduling Scenarios Favoring Min-Heaps","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"code":"$7e","fileName":"task_scheduler.py","language":"python"},"type":"code"},{"data":{"content":"**The semantic alignment:**\n\nNotice how the min-heap's behavior perfectly matches scheduling semantics:\n\n- **Most urgent** → smallest priority number → root of min-heap\n- **Next to run** → extract from min-heap → O(log n)\n- **New task arrives** → insert into min-heap → O(log n)\n\nThe data structure's natural behavior aligns with the problem's requirements without any artificial inversion or wrapper logic."},"type":"text"}],"titleType":"number","titleNumber":5},{"id":"graph-algorithms","title":"Graph Algorithms: A Deeper Look","content":[{"data":{"content":"We briefly mentioned Dijkstra's algorithm and Prim's algorithm earlier, but the connection between min-heaps and graph algorithms deserves deeper exploration. Understanding *why* these algorithms need min-heaps reveals fundamental insights about greedy optimization."},"type":"text"},{"data":{"items":["**Greedy algorithms make locally optimal choices** — At each step, they select the \"best\" available option without backtracking.","**\"Best\" often means \"smallest\"** — Shortest path (smallest distance), minimum spanning tree (smallest edge weight), lowest cost.","**Repeated extraction of minimum** — Greedy algorithms need to find and remove the smallest element over and over.","**Min-heap provides this efficiently** — O(log n) extraction, O(log n) insertion, O(1) peek at minimum."],"title":{"icon":"Waypoints","text":"The Greedy Selection Principle","type":"icon","color":"primary","variant":"outline-circle"},"variant":"glass"},"type":"list"},{"data":{"rows":[["Dijkstra's Algorithm","Path distance from source","(distance, vertex) pairs","Always expand closest vertex"],["Prim's Algorithm","Edge weight to tree","(weight, vertex) pairs","Always add cheapest edge"],["A* Search","f(n) = g(n) + h(n)","(f-value, node) pairs","Expand most promising node"],["Uniform Cost Search","Path cost","(cost, state) pairs","Explore cheapest path first"],["Best-First Search","Heuristic value","(h-value, node) pairs","Explore most promising first"]],"caption":"Graph Algorithms Using Min-Heaps","headers":["Algorithm","What's Minimized","Heap Contains","Why Min-Heap"]},"type":"table"},{"data":{"content":"**The unifying pattern:**\n\nAll these algorithms share a common structure:\n\n1. **Initialize** — Add starting element(s) to min-heap with initial cost/value\n2. **Extract minimum** — Pop the best candidate\n3. **Process** — Do work based on this candidate\n4. **Expand** — Add new candidates to heap with updated costs\n5. **Repeat** — Until heap is empty or goal is found\n\nThe min-heap is the backbone that makes this pattern efficient. Without it, step 2 would require O(n) scanning, making these algorithms impractically slow for large graphs."},"type":"text"},{"data":{"icon":"Lightbulb","title":"Implementation Insight","content":"In Dijkstra's algorithm, the same vertex might be added to the heap multiple times with different distances. Rather than implementing decrease-key (complex), we simply add duplicates and skip vertices when extracted if we've already found a shorter path. The min-heap naturally gives us the shortest path first.","variant":"tip"},"type":"callout"}],"titleType":"number","titleNumber":6},{"id":"real-world-systems","title":"Min-Heaps in Production Systems","content":[{"data":{"content":"Beyond academic algorithms, min-heaps power critical components of systems you use every day. Let's examine how production systems leverage min-heap semantics:"},"type":"text"},{"data":{"items":["**ORDER BY ... LIMIT K** — Databases use min-heaps (or max-heaps) to efficiently compute top-K results without sorting everything.","**Merge joins** — When joining sorted data from multiple sources (indexes, partitions), min-heaps merge the streams.","**External sorting** — Databases sort data larger than memory by sorting chunks, then merging them with a min-heap.","**Query cost estimation** — Some optimizers use heap-based priority queues to explore join orderings."],"title":{"icon":"Database","text":"Database Query Optimization","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"items":["**TCP Timer Management** — Linux kernel uses timer wheels, but conceptually manages \"next timeout\" with min-heap logic.","**Routing Protocols** — OSPF's shortest path first algorithm uses Dijkstra's algorithm with min-heaps.","**Load Balancer \"Least Connections\"** — Route to server with fewest active connections (smallest count).","**QoS Packet Scheduling** — Weighted fair queuing implementations use heap-like structures."],"title":{"icon":"Network","text":"Network Systems","type":"icon","color":"secondary","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"items":["**Memory Pool Allocators** — Track free blocks, potentially by size, to satisfy allocation requests.","**Disk I/O Schedulers** — Some elevator algorithms prioritize requests by sector to minimize seek time.","**Cache Eviction (LRU variants)** — Some LRU implementations use min-heaps keyed by access time.","**Connection Pool Management** — Return least-recently-used or lowest-latency connections."],"title":{"icon":"Gauge","text":"Resource Management","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"icon":"Eye","title":"The Invisible Infrastructure","content":"You rarely see min-heaps directly in application code because they're embedded in infrastructure: databases, operating systems, networking stacks. Understanding them helps you reason about system behavior and make better architectural decisions.","variant":"note"},"type":"callout"}],"titleType":"number","titleNumber":7},{"id":"decision-framework","title":"When to Choose Min-Heap: A Decision Framework","content":[{"data":{"content":"After exploring numerous applications, let's synthesize a practical decision framework. Ask yourself these questions when considering a min-heap:"},"type":"text"},{"data":{"type":"ordered","items":["**Do you need repeated access to the minimum element?** — Not just finding it once, but extracting it, then finding the new minimum, repeatedly.","**Is the collection dynamic?** — Elements are added and removed, not just searched. Static data might use sorting instead.","**Does \"minimum\" define your selection criteria?** — Earliest time, smallest cost, lowest priority number, shortest distance.","**Is O(log n) insertion acceptable?** — Heaps trade O(1) insertion (unsorted list) for O(1) minimum access.","**Do you NOT need to search for arbitrary elements?** — Heaps only give you the min efficiently, not arbitrary lookups."],"title":{"icon":"CircleHelp","text":"The Min-Heap Checklist","type":"icon","color":"primary","variant":"outline-circle"},"variant":"glass"},"type":"list"},{"data":{"rows":[["Find minimum","O(1)","Sorted array: O(1)","If data is static or insert-rarely"],["Insert element","O(log n)","Unsorted array: O(1)","If finding min is rare"],["Extract minimum","O(log n)","Sorted array: O(n)","Almost never for extract-heavy"],["Search for arbitrary element","O(n)","Hash set: O(1)","If you need membership testing"],["Find k-th smallest","O(k log n)","Selection algorithm: O(n)","One-time k-th element query"]],"caption":"Min-Heap vs Alternatives","headers":["Requirement","Min-Heap","Alternative","When to Use Alternative"]},"type":"table"},{"data":{"content":"**The golden rule:**\n\n**Use a min-heap when you repeatedly need to know \"what's next?\" and \"next\" means the smallest/earliest/cheapest option.**\n\nIf you only need the minimum once, sort or use selection. If you need it repeatedly in a dynamic collection, use a min-heap."},"type":"text"}],"titleType":"number","titleNumber":8},{"id":"summary","title":"Summary: Mastering Min-Heap Selection","content":[{"data":{"content":"We've thoroughly explored when and why to use min-heaps. Let's consolidate the key insights:"},"type":"text"},{"data":{"type":"ordered","items":["**Min-heaps surface the smallest element** — The root always holds the minimum, accessible in O(1) time.","**\"Smallest\" has many meanings** — Earliest time, lowest cost, highest urgency (when priority 1 > priority 5), shortest distance.","**Classic algorithm patterns** — Dijkstra, Prim, merge K sorted lists, Huffman coding—all rely on min-heaps for efficiency.","**Event-driven systems** — Simulations, schedulers, and timers use min-heaps to process events chronologically.","**Streaming K-largest** — Paradoxically, use a min-heap of size K to track the K largest elements in a stream.","**Graph algorithms** — Greedy optimization over shortest/cheapest paths naturally maps to min-heap extraction.","**Production systems** — Databases, networks, and OS kernels embed min-heap logic throughout their infrastructure."],"title":{"icon":"CheckCircle","text":"Key Takeaways","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"content":"**Looking ahead:**\n\nIn the next page, we'll explore the complementary perspective: **when to use max-heaps**. You'll discover how the same principles apply—but inverted—and learn to recognize problems where \"largest\" is the defining characteristic."},"type":"text"},{"data":{"icon":"CheckCircle","title":"Page Complete","content":"You now have deep intuition for min-heap use cases. The pattern is clear: when you repeatedly need the smallest/earliest/cheapest element from a dynamic collection, reach for a min-heap. Next, we'll see how max-heaps complement this with their own distinct use cases.","variant":"success"},"type":"callout"}],"titleType":"number","titleNumber":9}],"isLocked":false},{"id":"seed_cd3990da5f16b790b4930db260d55a55","title":"When to Use Max-Heap","order":1,"content":null,"isLocked":true},{"id":"seed_5716001a26aa6d7384f96b510b030538","title":"Converting Between Min-Heap and Max-Heap","order":2,"content":null,"isLocked":true},{"id":"seed_15c01d748a7f00b6a477c9b4b7996e1a","title":"Language-Specific Defaults","order":3,"content":null,"isLocked":true}]}}