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

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 (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 and 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 (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 (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 (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 (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) 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 (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 and thinkings/heap-2.md.

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

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 (lines 108‑118).

Median Finder (Two‑Heap Pattern)

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 (lines 78‑94).

Dijkstra’s Shortest Path (Priority Queue)

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 (lines 68‑69).

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

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 (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 (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 (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 (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 (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 (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.

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 (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, lines 78‑94), duplicate numbers are pushed into the appropriate heap based on value comparison, maintaining correct median calculation even with repeated values.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}