# Typical Usage Scenarios for Heap and Priority Queues: A Complete Guide

> Discover typical usage scenarios for heap and priority queues. Learn how these data structures excel at efficiently managing dynamic collections and extracting min/max elements. Get O(log N) insertion/deletion and O(1) extremum...

- Repository: [lucifer/leetcode](https://github.com/azl397985856/leetcode)
- Tags: how-to-guide
- Published: 2026-03-06

---

**A heap (priority queue) is the optimal data structure when you need to repeatedly extract the minimum or maximum element from a dynamically changing collection, offering O(1) access to the extremum and O(log N) insertion and deletion.**

In algorithmic problem solving, certain computational patterns demand efficient access to extreme values while the underlying dataset evolves in real time. The **azl397985856/leetcode** repository provides comprehensive documentation and reference implementations demonstrating typical usage scenarios for heap and priority queues across diverse challenges, from task scheduling to graph traversal. These data structures leverage the **heap invariant**—where each parent node is smaller (min-heap) or larger (max-heap) than its children—to guarantee constant-time access to the global extremum without scanning the entire collection.

## What Is a Heap and Why Use It?

A heap is a complete binary tree that satisfies the heap property: for a min-heap, every parent node’s key is less than or equal to its children’s keys (the inverse holds for a max-heap). This invariant ensures the root always contains the global minimum (or maximum), enabling **O(1)** peek operations.

Dynamic operations maintain this structure with **O(log N)** complexity:

- **Insertion**: Add the element at the next available position and "bubble up" (heapify-up).
- **Deletion**: Remove the root, replace it with the last element, and "bubble down" (heapify-down).

According to the repository’s analysis in [`thinkings/heap.md`](https://github.com/azl397985856/leetcode/blob/main/thinkings/heap.md) (lines 68‑69), this efficiency makes heaps indispensable for algorithms that process elements in order of urgency or cost while the candidate set grows or shrinks.

## Typical Usage Scenarios for Heap and Priority Queues

The repository’s detailed notes ([`thinkings/heap.md`](https://github.com/azl397985856/leetcode/blob/main/thinkings/heap.md) and [`thinkings/heap-2.md`](https://github.com/azl397985856/leetcode/blob/main/thinkings/heap-2.md)) enumerate specific domains where heaps provide optimal solutions. Below are the most common patterns found in the source code.

### Task and Job Scheduling

When assigning resources to jobs with varying priorities or virtual timestamps, a priority queue ensures the highest-priority (or earliest) job is always processed next. The repository describes a **registration system** (挂号系统) in [`thinkings/heap.md`](https://github.com/azl397985856/leetcode/blob/main/thinkings/heap.md) (lines 54‑85) where patients are served based on urgency scores.

**Implementation pattern**: Store `(priority, job_id)` tuples; `heappush` for enqueue, `heappop` for dequeue.

### Finding the K‑th Smallest or Largest Element

To find the k‑th order statistic in a stream or large dataset, maintain a **fixed-size heap** of capacity k. For the k‑th smallest, use a max-heap of size k to store the k smallest elements seen so far; the root is the answer.

The repository documents this as **"技巧一 ‑ 固定堆"** (Technique 1: Fixed Heap) in [`thinkings/heap-2.md`](https://github.com/azl397985856/leetcode/blob/main/thinkings/heap-2.md) (lines 108‑118).

### Median Maintenance in Data Streams

When calculating the running median of a dynamic sequence, use **two heaps**: a max-heap for the lower half and a min-heap for the upper half. Rebalance sizes so the max-heap has at most one more element than the min-heap, allowing O(1) median retrieval.

The `MedianFinder` class in [`thinkings/heap-2.md`](https://github.com/azl397985856/leetcode/blob/main/thinkings/heap-2.md) (lines 78‑94) implements this pattern with `O(log N)` per insertion.

### Dijkstra’s Shortest Path and Weighted BFS

Graph algorithms that expand nodes in order of increasing cost (like Dijkstra’s or A*) rely on a priority queue of `(tentative_distance, node)` tuples. The heap always extracts the unvisited node with the smallest distance, guaranteeing optimal paths.

As noted in [`thinkings/heap.md`](https://github.com/azl397985856/leetcode/blob/main/thinkings/heap.md) (lines 68‑69), this is the canonical application for heap-based graph traversal.

### Top‑K Frequent Elements and Greedy Allocation

Problems requiring the "best" or "worst" K items from a dynamic candidate pool—such as **minimum cost to hire K workers** (`mincostToHireWorkers`, lines 85‑102 in [`heap-2.md`](https://github.com/azl397985856/leetcode/blob/main/heap-2.md)) or **minimum refueling stops** (`minRefuelStops`, lines 113‑122)—use heaps to greedily select the optimal resource at each step while maintaining alternatives for future decisions.

### Multi‑Way Merge of Sorted Lists

When merging *m* sorted arrays or finding the k‑th smallest sum in a matrix, a heap stores the current head of each list along with its origin index. Repeatedly popping the smallest element and pushing its successor from the same list efficiently generates the global ordering without full materialization.

The repository provides a detailed implementation for **"有序矩阵第 k 小的数组和"** in [`thinkings/heap-2.md`](https://github.com/azl397985856/leetcode/blob/main/thinkings/heap-2.md) (lines 403‑434).

### Event Simulation with Future Timestamps

Discrete event simulations (e.g., **avoiding floods** in `avoidFlood`, lines 250‑268) use the heap as a chronological queue. Events are ordered by their trigger time, allowing the simulation to jump to the next relevant moment in O(log N) time.

## Implementation Patterns from the LeetCode Repository

The following self‑contained Python snippets demonstrate the most common heap patterns found in [`thinkings/heap.md`](https://github.com/azl397985856/leetcode/blob/main/thinkings/heap.md) and [`thinkings/heap-2.md`](https://github.com/azl397985856/leetcode/blob/main/thinkings/heap-2.md).

### Fixed‑Size K‑Heap (K‑th Smallest)

```python
import heapq

def kth_smallest(nums, k):
    # Max-heap simulation using negatives to find k-th smallest

    max_heap = []
    for x in nums:
        heapq.heappush(max_heap, -x)
        if len(max_heap) > k:
            heapq.heappop(max_heap)
    return -max_heap[0]

```

*Reference:* Technique "固定堆" in [`thinkings/heap-2.md`](https://github.com/azl397985856/leetcode/blob/main/thinkings/heap-2.md) (lines 108‑118).

### Median Finder (Two‑Heap Pattern)

```python
import heapq

class MedianFinder:
    def __init__(self):
        self.min_heap = []      # Upper half

        self.max_heap = []      # Lower half (stored as negatives)

    def addNum(self, num: int) -> None:
        if not self.max_heap or num < -self.max_heap[0]:
            heapq.heappush(self.max_heap, -num)
        else:
            heapq.heappush(self.min_heap, num)
        
        # Rebalance: max_heap can have at most 1 more element

        if len(self.max_heap) > len(self.min_heap) + 1:
            heapq.heappush(self.min_heap, -heapq.heappop(self.max_heap))
        elif len(self.min_heap) > len(self.max_heap):
            heapq.heappush(self.max_heap, -heapq.heappop(self.min_heap))

    def findMedian(self) -> float:
        if len(self.max_heap) == len(self.min_heap):
            return (self.min_heap[0] - self.max_heap[0]) / 2
        return -self.max_heap[0]

```

*Reference:* `MedianFinder` implementation in [`thinkings/heap-2.md`](https://github.com/azl397985856/leetcode/blob/main/thinkings/heap-2.md) (lines 78‑94).

### Dijkstra’s Shortest Path (Priority Queue)

```python
import heapq
from collections import defaultdict

def dijkstra(graph, start):
    """
    graph: dict mapping node -> list of (neighbor, weight)
    """
    dist = defaultdict(lambda: float('inf'))
    dist[start] = 0
    pq = [(0, start)]           # (distance, vertex)

    
    while pq:
        d, u = heapq.heappop(pq)
        if d != dist[u]:        # Skip stale entries

            continue
        for v, w in graph[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    return dist

```

*Reference:* Heap usage discussion in [`thinkings/heap.md`](https://github.com/azl397985856/leetcode/blob/main/thinkings/heap.md) (lines 68‑69).

### Multi‑Way Merge (K‑th Smallest Array Sum)

```python
import heapq

def kth_smallest_array_sum(mat, k):
    """
    Find k-th smallest sum of selecting one element from each row.
    mat: list of sorted lists (matrix)
    """
    m = len(mat)
    initial_sum = sum(row[0] for row in mat)
    initial_ptrs = tuple([0] * m)
    start_state = (initial_sum, initial_ptrs)
    
    heap = [start_state]
    seen = {initial_ptrs}
    
    for _ in range(k):
        cur_sum, ptr = heapq.heappop(heap)
        for i in range(m):
            if ptr[i] + 1 < len(mat[i]):
                new_ptr = list(ptr)
                new_ptr[i] += 1
                new_ptr_t = tuple(new_ptr)
                if new_ptr_t not in seen:
                    seen.add(new_ptr_t)
                    new_sum = cur_sum - mat[i][ptr[i]] + mat[i][ptr[i] + 1]
                    heapq.heappush(heap, (new_sum, new_ptr_t))
    return cur_sum

```

*Reference:* Multi‑way merge implementation in [`thinkings/heap-2.md`](https://github.com/azl397985856/leetcode/blob/main/thinkings/heap-2.md) (lines 403‑434).

## Summary

- **Heaps** maintain the extremum (min or max) at the root, enabling **O(1)** peek and **O(log N)** insertion/deletion.
- **Task scheduling** and **event simulation** rely on priority queues to process items by urgency or timestamp, as demonstrated in [`thinkings/heap.md`](https://github.com/azl397985856/leetcode/blob/main/thinkings/heap.md) (lines 54‑85).
- **Order statistics** (k‑th smallest/largest) use **fixed‑size heaps** to bound memory and achieve streaming computation, documented in [`thinkings/heap-2.md`](https://github.com/azl397985856/leetcode/blob/main/thinkings/heap-2.md) (lines 108‑118).
- **Median maintenance** employs **two heaps** (max‑heap for lower half, min‑heap for upper half) to balance dynamic datasets, implemented in [`thinkings/heap-2.md`](https://github.com/azl397985856/leetcode/blob/main/thinkings/heap-2.md) (lines 78‑94).
- **Graph algorithms** like **Dijkstra’s shortest path** use priority queues of `(distance, node)` tuples to greedily expand the frontier, referenced in [`thinkings/heap.md`](https://github.com/azl397985856/leetcode/blob/main/thinkings/heap.md) (lines 68‑69).
- **Multi‑way merging** of sorted sequences uses a heap to track the current head of each list, enabling efficient k‑way merge and smallest‑sum matrix problems, detailed in [`thinkings/heap-2.md`](https://github.com/azl397985856/leetcode/blob/main/thinkings/heap-2.md) (lines 403‑434).

## Frequently Asked Questions

### When should I use a heap instead of sorting?

Use a heap when your dataset is **dynamic** (elements arrive or depart over time) or when you only need the **top‑K** elements rather than a full ordering. Sorting requires **O(N log N)** upfront and **O(N)** space, whereas a heap processes streaming data in **O(N log K)** time with **O(K)** space, as shown in the fixed‑heap technique in [`thinkings/heap-2.md`](https://github.com/azl397985856/leetcode/blob/main/thinkings/heap-2.md).

### How do I implement a max‑heap in Python?

Python’s `heapq` module provides a min‑heap by default. To simulate a **max‑heap**, store **negated values** (push `-x` and pop `-x`). For example, when finding the k‑th smallest element using a fixed‑size heap of size k, the repository stores negatives in `max_heap` to keep the largest of the k smallest at the root, as demonstrated in [`thinkings/heap-2.md`](https://github.com/azl397985856/leetcode/blob/main/thinkings/heap-2.md) (lines 108‑118).

### What is the time complexity of building a heap from an array?

Building a heap from an arbitrary array using the **bottom‑up heapify** approach takes **O(N)** time, which is more efficient than inserting N elements individually (**O(N log N)**). This optimization is crucial for algorithms like **Dijkstra’s** or **HeapSort** where initialization performance matters, though the repository’s Python examples typically use incremental `heappush` for clarity in problem‑solving contexts.

### Can a priority queue handle duplicate values?

Yes, heaps and priority queues **naturally handle duplicates** because they rely on key comparisons rather than uniqueness constraints. When duplicate priorities exist, the extraction order among equals depends on the implementation (typically FIFO for stable heaps or arbitrary for standard binary heaps). In the repository’s **MedianFinder** implementation ([`thinkings/heap-2.md`](https://github.com/azl397985856/leetcode/blob/main/thinkings/heap-2.md), lines 78‑94), duplicate numbers are pushed into the appropriate heap based on value comparison, maintaining correct median calculation even with repeated values.