Heaps and Priority Queues

Chapter 12: Heaps and Priority Queues

In the previous chapter, we studied binary search trees, which support efficient search, insertion, and deletion. But there is a class of problems that does not require maintaining a total order — you only care about "what is the current minimum (or maximum) element?" For example: an OS needs to schedule the highest-priority process, Dijkstra's algorithm needs to extract the nearest node, or a real-time data stream needs to continuously track the median.

The heap is a data structure designed for exactly this "fast extremum retrieval" scenario. It only guarantees that each parent node is "better" (smaller or larger) than its children, without maintaining a complete ordering. This "weaker" constraint yields excellent performance: insert O(log n), peek at extremum O(1), delete extremum O(log n) — and a heap can be implemented with a simple array, no pointers needed.

A priority queue is the abstract interface of a heap: insert an element, extract the element with the highest priority. Nearly every language's standard library provides a priority queue implementation — Python's heapq, Java's PriorityQueue, C++'s priority_queue.

This chapter's goals: (1) thoroughly understand the structure and operation principles of heaps; (2) become proficient with Python's heapq module for solving real problems; (3) master the heapsort algorithm; (4) recognize "need a heap" scenarios in interviews and engineering.

Level 1 · What You Need to Know

12.1 The Heap Concept

A heap is a complete binary tree that satisfies the heap property:

• Min-Heap: Every node's value is ≤ its children's values. The root is the global minimum.
• Max-Heap: Every node's value is ≥ its children's values. The root is the global maximum.

What is a complete binary tree? All levels are fully filled except possibly the last, and the last level's nodes are packed from left to right (no gaps).

Min-heap example:
         1
       /   \
      3     2
     / \   /
    7   4  5

Heap property: every parent ≤ its children
Root node 1 is the global minimum
Note: there is no ordering between 3 and 2 — heaps do not guarantee sibling order

Core insight: A heap is a "partial order" structure. It only guarantees parent-child relationships, not ordering among same-level nodes. This is much weaker than BST's "total order," but it yields a simpler implementation and better cache performance.

12.2 Array Representation

Complete binary trees have a beautiful property: they can be represented compactly in an array with no pointers needed.

If we number the nodes of a complete binary tree in level-order (top-to-bottom, left-to-right) as 0, 1, 2, ..., then:

• Parent index: parent(i) = (i - 1) // 2
• Left child index: left(i) = 2 * i + 1
• Right child index: right(i) = 2 * i + 2

Array:  [1, 3, 2, 7, 4, 5]
Index:   0  1  2  3  4  5

Corresponding tree:
         1(0)
       /      \
     3(1)    2(2)
    /   \    /
  7(3) 4(4) 5(5)

Verification:
- Node 3 has index 1, parent = (1-1)//2 = 0 → value 1 ✓
- Node 3's left child = 2*1+1 = 3 → value 7 ✓
- Node 3's right child = 2*1+2 = 4 → value 4 ✓

Why is the array representation good?

1. Zero extra space: No left/right pointers needed, each node stores only the value
2. Cache-friendly: Array elements are contiguous in memory, enabling efficient CPU prefetching
3. O(1) index computation: Simple arithmetic (or bit operations) to find parent/children

This is the fundamental reason heaps are much faster in practice than pointer-based binary trees (BST, AVL tree) — not better asymptotic complexity, but much smaller constant factors.

12.3 Core Heap Operations

A heap needs only two core operations: sift up and sift down. All higher-level operations (insert, delete, build) are built upon these two.

sift_up: Float a New Element Up

When we insert a new element at the end of the heap, it may be smaller than its parent (violating the min-heap property). We repeatedly "float it up" until it finds its correct position.

def sift_up(heap, i):
    """Float element at index i up to its correct position (min-heap)"""
    while i > 0:
        parent = (i - 1) // 2
        if heap[i] < heap[parent]:
            heap[i], heap[parent] = heap[parent], heap[i]
            i = parent
        else:
            break  # heap property satisfied

Complexity: Worst case floats from leaf to root, traversing O(log n) levels.

sift_down: Sink the Root Element Down

When we delete the top (extract minimum), we place the last element at the root. It may be larger than its children (violating heap property). We repeatedly "sink it down," each time swapping with the smaller child.

def sift_down(heap, i, size):
    """Sink element at index i down to its correct position (min-heap)"""
    while True:
        smallest = i
        left = 2 * i + 1
        right = 2 * i + 2
        
        if left < size and heap[left] < heap[smallest]:
            smallest = left
        if right < size and heap[right] < heap[smallest]:
            smallest = right
        
        if smallest == i:
            break  # heap property satisfied
        
        heap[i], heap[smallest] = heap[smallest], heap[i]
        i = smallest

Why swap with the smaller child? After swapping, smallest becomes the new parent, and it must be smaller than both children. If we swapped with the larger child, it might be larger than the other child, violating the heap property.

Complexity: Worst case sinks from root to leaf, O(log n).

Insert Operation

def heap_insert(heap, val):
    """Insert an element into the min-heap"""
    heap.append(val)               # place at end (maintains complete tree shape)
    sift_up(heap, len(heap) - 1)   # float up to correct position

Extract-Min Operation

def heap_extract_min(heap):
    """Extract and return the minimum from the min-heap"""
    if not heap:
        raise IndexError("heap is empty")
    
    min_val = heap[0]
    # Replace root with last element
    heap[0] = heap[-1]
    heap.pop()
    # Sink the new root
    if heap:
        sift_down(heap, 0, len(heap))
    
    return min_val

Why replace root with the last element? Directly removing the root would destroy the complete binary tree structure. Filling the root position with the last element only requires one sift_down to restore the heap property while maintaining the complete tree shape.

12.4 Python's heapq Module

Python's standard library heapq module provides heap operation functions that work directly on lists (the list itself is the heap's array representation).

import heapq

# Create a heap
heap = []
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
heapq.heappush(heap, 2)
print(heap)  # [1, 3, 2] — minimum at heap[0]

# Pop minimum
min_val = heapq.heappop(heap)
print(min_val)  # 1
print(heap)     # [2, 3]

# Convert a regular list to a heap (in-place, O(n))
data = [5, 3, 8, 1, 2, 7]
heapq.heapify(data)
print(data)  # [1, 2, 7, 5, 3, 8] — note: NOT sorted! Only satisfies heap property

# Peek at top without popping
print(data[0])  # 1 — direct index access

# nlargest / nsmallest — find top K largest/smallest
nums = [5, 3, 8, 1, 2, 7, 4, 6]
print(heapq.nlargest(3, nums))   # [8, 7, 6]
print(heapq.nsmallest(3, nums))  # [1, 2, 3]

Key heapq features:

12.5 Max-Heap: The Negation Trick

Python heapq only supports min-heaps. If you need a max-heap, the standard approach is to negate values:

import heapq

# Max-heap: store -val, negate again on extraction
max_heap = []
heapq.heappush(max_heap, -5)
heapq.heappush(max_heap, -3)
heapq.heappush(max_heap, -8)

# Extract maximum
max_val = -heapq.heappop(max_heap)
print(max_val)  # 8

For tuples:

# Max-heap by priority: (priority, task)
tasks = []
heapq.heappush(tasks, (-priority, task_id, task))

# Extract highest priority
neg_pri, tid, task = heapq.heappop(tasks)
actual_priority = -neg_pri

12.6 The Top-K Problem

Problem: Find the K largest (or smallest) elements from n elements.

Approach 1: Sort — O(n log n), simple but wasteful when K << n.

Approach 2: Min-heap of size K — O(n log K), the best balanced solution.

Core idea: Maintain a min-heap of size K, where the top is "the smallest among the K largest elements seen so far." Scan all elements; if the current element is larger than the heap top, replace the top.

import heapq

def top_k_largest(nums, k):
    """Find the K largest elements in the array"""
    if k >= len(nums):
        return sorted(nums, reverse=True)
    
    # Method 1: Use nlargest (recommended)
    return heapq.nlargest(k, nums)

def top_k_largest_manual(nums, k):
    """Manually maintain a min-heap of size K"""
    # Initialize: take first K elements and heapify
    heap = nums[:k]
    heapq.heapify(heap)
    
    # Scan remaining elements
    for num in nums[k:]:
        if num > heap[0]:  # larger than threshold, replace
            heapq.heapreplace(heap, num)
    
    return sorted(heap, reverse=True)

# Example
nums = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
print(top_k_largest(nums, 3))         # [9, 6, 5]
print(top_k_largest_manual(nums, 3))  # [9, 6, 5]

Why use a min-heap to find the K largest? Counter-intuitive but clever:

• The min-heap's top is the smallest element in the heap
• The heap holds "the K largest elements seen so far"
• The heap top is the threshold (minimum) of these K elements
• A new element can only enter the "top K" if it exceeds this threshold

If you used a max-heap, you would need to put all n elements in and then pop K times — O(n) space. The min-heap only needs O(K) space.

LeetCode #215 — Kth Largest Element in an Array:

def findKthLargest(nums, k):
    """Return the kth largest element in the array"""
    # Method 1: heapq.nlargest (most direct)
    return heapq.nlargest(k, nums)[-1]
    
    # Method 2: maintain a min-heap of size K
    # heap = nums[:k]
    # heapq.heapify(heap)
    # for num in nums[k:]:
    #     if num > heap[0]:
    #         heapq.heapreplace(heap, num)
    # return heap[0]

12.7 Common Usage Patterns Summary

import heapq

# Pattern 1: Event scheduling (ordered by timestamp)
events = []
heapq.heappush(events, (timestamp, event_type, data))

# Pattern 2: Multi-way merge (from multiple sorted sources)
# heapq.merge(*sorted_iterables)  # returns lazy iterator

# Pattern 3: Priority queue with deferred deletion
# Mark deleted elements, skip them on pop
removed = set()
while heap:
    val = heapq.heappop(heap)
    if val not in removed:
        process(val)
        break

Level 2 · How It Works Internally

12.8 Complete Heap Implementation from Scratch

Here is a full min-heap class implementation, showing the internal logic of each operation:

class MinHeap:
    """Complete min-heap implementation"""
    
    def __init__(self):
        self._data = []
    
    def __len__(self):
        return len(self._data)
    
    def __bool__(self):
        return len(self._data) > 0
    
    def peek(self):
        """View top element, O(1)"""
        if not self._data:
            raise IndexError("heap is empty")
        return self._data[0]
    
    def insert(self, val):
        """Insert element, O(log n)"""
        self._data.append(val)
        self._sift_up(len(self._data) - 1)
    
    def extract_min(self):
        """Extract and return minimum, O(log n)"""
        if not self._data:
            raise IndexError("heap is empty")
        
        min_val = self._data[0]
        last = self._data.pop()
        if self._data:
            self._data[0] = last
            self._sift_down(0)
        return min_val
    
    def _sift_up(self, i):
        """Sift up operation"""
        while i > 0:
            parent = (i - 1) // 2
            if self._data[i] < self._data[parent]:
                self._data[i], self._data[parent] = self._data[parent], self._data[i]
                i = parent
            else:
                break
    
    def _sift_down(self, i):
        """Sift down operation"""
        n = len(self._data)
        while True:
            smallest = i
            left = 2 * i + 1
            right = 2 * i + 2
            
            if left < n and self._data[left] < self._data[smallest]:
                smallest = left
            if right < n and self._data[right] < self._data[smallest]:
                smallest = right
            
            if smallest == i:
                break
            
            self._data[i], self._data[smallest] = self._data[smallest], self._data[i]
            i = smallest
    
    @classmethod
    def build_heap(cls, items):
        """Build heap from list, O(n)"""
        heap = cls()
        heap._data = list(items)
        # Bottom-up: sift_down from last non-leaf node
        n = len(heap._data)
        for i in range(n // 2 - 1, -1, -1):
            heap._sift_down(i)
        return heap
    
    def __repr__(self):
        return f"MinHeap({self._data})"


# Usage example
heap = MinHeap()
for val in [5, 3, 8, 1, 2, 7]:
    heap.insert(val)
print(heap)  # MinHeap([1, 2, 7, 5, 3, 8])

while heap:
    print(heap.extract_min(), end=" ")  # 1 2 3 5 7 8

12.9 Proof of O(n) build_heap Complexity

Intuitively, building a heap should take O(n log n) — n elements each doing O(log n) sift_down. But in reality, bottom-up heap construction takes O(n) total time.

Key observation: Nodes at different levels have different sift_down costs.

Let the heap have h = floor(log₂n) levels (numbered from 0):

• Level 0 (root): 1 node, sift_down traverses at most h steps
• Level 1: 2 nodes, sift_down traverses at most h-1 steps
• Level k: 2^k nodes, sift_down traverses at most h-k steps
• Level h-1: 2^(h-1) nodes, sift_down traverses at most 1 step
• Level h (leaves): approximately n/2 nodes, no sift_down needed

Total work:

T(n) = Σ(k=0 to h-1) 2^k × (h - k)

Let j = h - k (levels counted from the bottom):

T(n) = Σ(j=1 to h) 2^(h-j) × j
     = 2^h × Σ(j=1 to h) j / 2^j

The series Σ(j=1 to ∞) j/2^j converges to 2 (a classic power series result).

Therefore T(n) ≤ 2^h × 2 = 2^(h+1) = O(n).

Intuitive explanation: Leaf nodes account for nearly half of all nodes, but they require zero work. Nodes near the bottom are numerous but move short distances; nodes near the top move long distances but are very few. This "most nodes do little work" pattern makes the sum converge to O(n).

Why not top-down heap building? If we call insert (i.e., sift_up) for each element, then at level k there are 2^k nodes, each floating up k steps, total Σ k×2^k = O(n log n). The top-down pattern is the opposite — "few nodes do little work, many nodes do lots of work" — so it is slower.

12.10 Heapsort

Heapsort was invented by J.W.J. Williams in 1964 (along with the heap data structure itself). It is an in-place sorting algorithm with worst-case O(n log n), requiring no extra space.

Algorithm steps:

1. Build a max-heap from the array in-place: O(n)
2. Repeat n-1 times: swap the root (maximum) with the last element, reduce heap size by 1, sift_down the new root

def heap_sort(arr):
    """Heapsort: in-place, unstable, O(n log n)"""
    n = len(arr)
    
    # Step 1: Build max-heap (bottom-up)
    for i in range(n // 2 - 1, -1, -1):
        _sift_down_max(arr, i, n)
    
    # Step 2: Repeatedly extract maximum to the end
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]  # swap root with end
        _sift_down_max(arr, 0, i)         # sift_down on reduced heap


def _sift_down_max(arr, i, size):
    """Max-heap sift_down"""
    while True:
        largest = i
        left = 2 * i + 1
        right = 2 * i + 2
        
        if left < size and arr[left] > arr[largest]:
            largest = left
        if right < size and arr[right] > arr[largest]:
            largest = right
        
        if largest == i:
            break
        
        arr[i], arr[largest] = arr[largest], arr[i]
        i = largest


# Example
data = [5, 3, 8, 1, 2, 7, 4, 6]
heap_sort(data)
print(data)  # [1, 2, 3, 4, 5, 6, 7, 8]

Heapsort performance analysis:

Heapsort vs Quicksort vs Mergesort:

• Quicksort: Fastest on average (small constant factor, cache-friendly), but O(n²) worst case
• Mergesort: Stable, guaranteed O(n log n), but requires O(n) extra space
• Heapsort: Guaranteed O(n log n) + in-place, but poor cache behavior (jumping access patterns)

In practice, heapsort is rarely used for general-purpose sorting (quicksort is faster), but it is valuable when you need strict space constraints + worst-case guarantees (e.g., Linux kernel's sort function uses introsort, which falls back to heapsort when recursion depth is excessive).

12.11 Merging K Sorted Lists (LeetCode #23)

Problem: Given K sorted linked lists, merge them into one sorted linked list.

Brute force: Each round finds the minimum among K list heads, requiring K comparisons. Total N nodes → O(NK).

Heap optimization: Use a min-heap to maintain the current head nodes of all K lists. Each time extract the heap top (global minimum), then push that list's next node into the heap.

import heapq

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def mergeKLists(lists):
    """Merge K sorted lists. Time O(N log K), Space O(K)"""
    # Min-heap: (node value, list index, node)
    # List index breaks ties when values are equal
    heap = []
    
    for i, head in enumerate(lists):
        if head:
            heapq.heappush(heap, (head.val, i, head))
    
    dummy = ListNode(0)
    curr = dummy
    
    while heap:
        val, i, node = heapq.heappop(heap)
        curr.next = node
        curr = curr.next
        
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))
    
    return dummy.next

Complexity analysis:

• Time: O(N log K), where N is total number of nodes, K is number of lists. Each node enters and exits the heap once, each time O(log K).
• Space: O(K), at most K elements in the heap.

Why use list index i? Python's heapq compares tuples field by field. If two nodes have equal values, it compares the second field. ListNode doesn't define __lt__, so direct comparison raises an error. A unique index i breaks the tie.

12.12 Find Median from Data Stream (LeetCode #295)

Problem: Design a data structure that supports:

• addNum(num): Add an integer from the data stream
• findMedian(): Return the median of all numbers added so far

Core idea: Use two heaps to split data into two halves:

• Max-heap lo: Stores the smaller half (top is the maximum of this half)
• Min-heap hi: Stores the larger half (top is the minimum of this half)

Maintain constraint: len(lo) == len(hi) or len(lo) == len(hi) + 1

Median = top of lo (odd count), or (top of lo + top of hi) / 2 (even count).

import heapq

class MedianFinder:
    def __init__(self):
        self.lo = []  # max-heap (store negated values): smaller half
        self.hi = []  # min-heap: larger half
    
    def addNum(self, num):
        # First add to max-heap
        heapq.heappush(self.lo, -num)
        
        # Ensure max of lo ≤ min of hi
        if self.hi and (-self.lo[0] > self.hi[0]):
            val = -heapq.heappop(self.lo)
            heapq.heappush(self.hi, val)
        
        # Ensure len(lo) >= len(hi) (lo has at most one more than hi)
        if len(self.lo) < len(self.hi):
            val = heapq.heappop(self.hi)
            heapq.heappush(self.lo, -val)
        
        # Ensure lo doesn't have more than one extra over hi
        if len(self.lo) > len(self.hi) + 1:
            val = -heapq.heappop(self.lo)
            heapq.heappush(self.hi, val)
    
    def findMedian(self):
        if len(self.lo) > len(self.hi):
            return -self.lo[0]
        return (-self.lo[0] + self.hi[0]) / 2


# Usage example
mf = MedianFinder()
mf.addNum(1)    # [1]         → median = 1
mf.addNum(2)    # [1, 2]      → median = 1.5
mf.addNum(3)    # [1, 2, 3]   → median = 2
print(mf.findMedian())  # 2
mf.addNum(4)    # [1, 2, 3, 4] → median = 2.5
print(mf.findMedian())  # 2.5

Complexity:

• addNum: O(log n) — at most three heap operations
• findMedian: O(1) — direct access to heap tops

Why is the two-heap approach so elegant? The median divides data into two equal halves. The max-heap's top is "the largest of the smaller half," and the min-heap's top is "the smallest of the larger half" — they are exactly the left and right neighbors of the median.

12.13 Priority Queue in Dijkstra's Algorithm

Dijkstra's algorithm for single-source shortest paths needs to find "the unconfirmed node with the smallest distance" each round. This is exactly where a priority queue shines.

import heapq

def dijkstra(graph, start):
    """
    Dijkstra's shortest path algorithm (priority queue implementation)
    graph: adjacency list {node: [(neighbor, weight), ...]}
    Returns: {node: shortest_distance}
    """
    dist = {start: 0}
    heap = [(0, start)]  # (distance, node)
    visited = set()
    
    while heap:
        d, u = heapq.heappop(heap)
        
        if u in visited:
            continue  # shortest distance already confirmed, skip
        visited.add(u)
        
        for v, w in graph.get(u, []):
            new_dist = d + w
            if v not in dist or new_dist < dist[v]:
                dist[v] = new_dist
                heapq.heappush(heap, (new_dist, v))
    
    return dist


# Example
graph = {
    'A': [('B', 1), ('C', 4)],
    'B': [('C', 2), ('D', 5)],
    'C': [('D', 1)],
    'D': []
}
print(dijkstra(graph, 'A'))  # {'A': 0, 'B': 1, 'C': 3, 'D': 4}

Note: This implementation uses "lazy deletion" — the same node may appear multiple times in the heap (since we lack a decrease-key operation). Correctness is ensured by the visited set, which skips already-processed nodes.

Complexity: With a binary heap, Dijkstra runs in O((V + E) log V). With a Fibonacci heap (supporting O(1) decrease-key), it can be optimized to O(V log V + E) — but in practice binary heaps are usually faster due to smaller constant factors.

For a complete discussion of graph algorithms, see Chapter 18.

Level 3 · What the Specification Says

12.14 History of the Binary Heap

The binary heap was invented by J.W.J. Williams in 1964, published in "Algorithm 232: Heapsort" (Communications of the ACM, Vol. 7, No. 6, June 1964). Williams simultaneously introduced both the heap data structure and the heapsort algorithm — a rare event in computer science history where a data structure and its primary application are born in the same paper.

That same year, Robert W. Floyd in "Algorithm 245: Treesort 3" (Communications of the ACM, Vol. 7, No. 12, December 1964) improved Williams' method by proposing the O(n) bottom-up heap construction algorithm. Floyd's contribution kept heapsort's total time complexity at O(n log n) while reducing the heap building phase from O(n log n) to O(n).

These two papers established the heap's foundational position in algorithms. For sixty years since, the binary heap has remained the standard method for implementing priority queues — simple, efficient, and space-compact.

12.15 Fibonacci Heaps

In 1987, Michael L. Fredman and Robert E. Tarjan proposed the Fibonacci heap in their paper "Fibonacci heaps and their uses in improved network optimization algorithms" (Journal of the ACM, Vol. 34, No. 3, July 1987).

Motivation: In Dijkstra's and Prim's algorithms, the frequently executed operation is decrease-key (lowering some node's priority). In a binary heap, decrease-key requires O(log n) (find the element, then sift_up). If decrease-key could be reduced to O(1) amortized, the entire algorithm becomes faster.

Fibonacci heap operation complexities:

Core idea: A Fibonacci heap is a collection of "unordered" heap-ordered trees. Insert and decrease-key are "lazy" — they do the minimum amount of structural adjustment, deferring real restructuring to extract-min. This "deferred consolidation" strategy means extract-min might be slow (O(n) worst case), but amortized it remains O(log n).

Why "Fibonacci"? The structural constraint maintained by cascading cut operations guarantees that a subtree of degree d contains at least F(d+2) nodes (where F is the Fibonacci sequence). This ensures the maximum degree is O(log n), thereby guaranteeing the O(log n) amortized complexity of extract-min.

Practical status: Despite being theoretically superior, Fibonacci heaps are rarely used in practice because:

1. Large constant factors (each node maintains parent, child, left, right pointers plus degree and mark flags)
2. Poor cache performance (pointer structures cause memory jumping)
3. Complex implementation, prone to bugs
4. For practical graph sizes (up to several million nodes), binary heap + lazy deletion is usually faster

However, Fibonacci heaps remain crucial in theoretical algorithm analysis — they provide optimal complexity upper bounds for many graph algorithms.

12.16 d-ary Heaps

The standard binary heap has 2 children per node. A natural generalization is the d-ary heap: each node has d children.

Array representation:

• parent(i) = (i - 1) // d
• child_k(i) = d * i + k + 1 (k = 0, 1, ..., d-1)

Complexity changes:

• sift_up: Tree height becomes log_d(n), so O(log_d(n)) = O(log n / log d) — faster
• sift_down: Each level requires comparing d children to find the minimum, so O(d × log_d(n)) — potentially slower

Optimal choice:

• If decrease-key (sift_up) operations vastly outnumber extract-min (sift_down), increasing d helps
• In Dijkstra's algorithm, decrease-key happens at most E times, extract-min at most V times. When E >> V, using d = E/V gives O(E log_{E/V} V) complexity

In practice: d = 4 (quaternary heap) is a common optimization choice. A 4-ary heap is flatter than a binary heap, reducing sift_up levels; meanwhile comparing 4 children per level can be well-optimized on modern CPUs (SIMD instructions). LevelDB and certain Java implementations use quaternary heaps.

12.17 Heaps in Operating Systems

Timer Management

Operating systems manage numerous timers (network timeouts, process time slices, periodic tasks, etc.). The core operation is "find the timer that will fire soonest" — a textbook min-heap application.

The Linux kernel originally used linked lists for timer management (O(1) insertion but O(n) to find the nearest expiring timer), later evolving to hierarchical timing wheels and red-black tree schemes. But in userspace (libuv, Go runtime), heaps remain the primary data structure for timer management.

Go runtime's timer heap: Before Go 1.14, a global quaternary heap managed all goroutine timers. After 1.14, each P (processor) maintains a local quaternary heap, reducing lock contention.

Process Scheduling

In priority scheduling algorithms, ready processes are arranged by priority, with the highest-priority process selected to run each time. This can be implemented with a max-heap. However, modern operating systems (like Linux's CFS scheduler) use red-black trees instead of heaps because they need efficient "find the process with the smallest virtual runtime" along with arbitrary deletion support.

Memory Allocation

Some memory allocators use heaps to manage free blocks, sorted by block size, to quickly find the smallest (best-fit) or largest (worst-fit) free block satisfying a request.

Level 4 · Edge Cases and Pitfalls

12.18 Pitfalls of heapq

Pitfall 1: No decrease-key

Python heapq has no direct decrease-key operation. If you need to modify the priority of an element already in the heap, there are two strategies:

Strategy 1: Lazy deletion (recommended)

import heapq

class LazyPriorityQueue:
    """Priority queue with priority updates via lazy deletion"""
    
    def __init__(self):
        self._heap = []
        self._entry_finder = {}  # key -> [priority, key, valid]
        self._counter = 0
    
    def push(self, key, priority):
        """Insert or update key's priority"""
        if key in self._entry_finder:
            # Mark old entry as invalid
            self._entry_finder[key][-1] = False
        
        entry = [priority, self._counter, key, True]
        self._counter += 1
        self._entry_finder[key] = entry
        heapq.heappush(self._heap, entry)
    
    def pop(self):
        """Pop the valid element with highest priority (smallest value)"""
        while self._heap:
            priority, count, key, valid = heapq.heappop(self._heap)
            if valid:
                del self._entry_finder[key]
                return key, priority
        raise KeyError("priority queue is empty")
    
    def __contains__(self, key):
        return key in self._entry_finder and self._entry_finder[key][-1]


# Usage example
pq = LazyPriorityQueue()
pq.push('task_a', 5)
pq.push('task_b', 3)
pq.push('task_a', 1)  # Update task_a's priority to 1
print(pq.pop())  # ('task_a', 1) — correctly returns updated priority
print(pq.pop())  # ('task_b', 3)

Cost: The heap may accumulate many invalid entries, increasing space and time overhead. If decrease-key is very frequent, consider using sortedcontainers.SortedList instead.

Pitfall 2: No remove

heapq has no efficient remove-by-value operation. list.remove(val) is O(n), and after removal you need to re-heapify. The same solution is lazy deletion.

Pitfall 3: Tuple comparison rules

import heapq

# Correct: first tuple element is a comparable priority
heap = []
heapq.heappush(heap, (1, "task_a"))
heapq.heappush(heap, (2, "task_b"))  # ✓

# Dangerous: if priorities are equal, Python compares the second element
heapq.heappush(heap, (1, "task_c"))  # May be OK (strings are comparable)

# Error: second element not comparable raises error
class Task:
    def __init__(self, name):
        self.name = name

# heapq.heappush(heap, (1, Task("x")))
# heapq.heappush(heap, (1, Task("y")))
# TypeError: '<' not supported between instances of 'Task' and 'Task'

# Solution: add a unique counter as tiebreaker
counter = 0
def push_task(heap, priority, task):
    global counter
    counter += 1
    heapq.heappush(heap, (priority, counter, task))

Pitfall 4: heapq is a min-heap, but interviews often want max-heap

# Wrong: forgetting to negate
import heapq
heap = [1, 2, 3, 4, 5]
heapq.heapify(heap)
print(heapq.heappop(heap))  # 1, not 5!

# Correct: negate for max-heap
max_heap = [-x for x in [1, 2, 3, 4, 5]]
heapq.heapify(max_heap)
print(-heapq.heappop(max_heap))  # 5

12.19 High-Frequency Interview Problems

Problem 1: Find Median from Data Stream (LeetCode #295)

Already covered in detail in Section 12.12. Core technique: two heaps maintaining dynamic data's median.

Interview follow-ups:

• Q: What if the data stream has many duplicate values? A: No issue — heaps naturally support duplicates.
• Q: What if you need to support deleting a specific value? A: Use lazy deletion + maintain effective sizes of both heaps.
• Q: What if the data range is limited (e.g., 0-100)? A: Use counting sort/buckets, O(1) to find median.

Problem 2: Top K Frequent Elements (LeetCode #347)

import heapq
from collections import Counter

def topKFrequent(nums, k):
    """Return the K most frequent elements"""
    count = Counter(nums)
    # Method 1: nlargest
    return heapq.nlargest(k, count.keys(), key=count.get)
    
    # Method 2: min-heap of size K
    # return [item for item, freq in heapq.nlargest(k, count.items(), key=lambda x: x[1])]


# Example
print(topKFrequent([1,1,1,2,2,3], 2))  # [1, 2]

Method 3 (optimal): Bucket sort O(n)

def topKFrequent_bucket(nums, k):
    """Bucket sort method, O(n)"""
    count = Counter(nums)
    # Buckets: index is frequency, value is list of elements with that frequency
    buckets = [[] for _ in range(len(nums) + 1)]
    for num, freq in count.items():
        buckets[freq].append(num)
    
    result = []
    for freq in range(len(buckets) - 1, -1, -1):
        for num in buckets[freq]:
            result.append(num)
            if len(result) == k:
                return result
    return result

Problem 3: Ugly Number II (LeetCode #264)

Problem: Find the nth ugly number (positive integers whose prime factors only include 2, 3, 5: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, ...).

import heapq

def nthUglyNumber(n):
    """Min-heap approach"""
    heap = [1]
    seen = {1}
    
    for _ in range(n):
        ugly = heapq.heappop(heap)
        for factor in [2, 3, 5]:
            new_ugly = ugly * factor
            if new_ugly not in seen:
                seen.add(new_ugly)
                heapq.heappush(heap, new_ugly)
    
    return ugly


# More optimal three-pointer method (O(n) time, O(n) space)
def nthUglyNumber_dp(n):
    """Dynamic programming + three pointers"""
    dp = [0] * n
    dp[0] = 1
    p2 = p3 = p5 = 0  # three pointers
    
    for i in range(1, n):
        next2, next3, next5 = dp[p2] * 2, dp[p3] * 3, dp[p5] * 5
        dp[i] = min(next2, next3, next5)
        if dp[i] == next2: p2 += 1
        if dp[i] == next3: p3 += 1
        if dp[i] == next5: p5 += 1
    
    return dp[n - 1]


print(nthUglyNumber(10))     # 12
print(nthUglyNumber_dp(10))  # 12

Heap approach complexity: O(n log n) — each ugly number enters and exits the heap once. The three-pointer method is better: O(n) time.

Problem 4: Meeting Rooms II (LeetCode #253)

Problem: Given a list of meeting start and end times, find the minimum number of meeting rooms required.

import heapq

def minMeetingRooms(intervals):
    """
    Greedy + min-heap
    The heap stores end times of currently occupied rooms
    """
    if not intervals:
        return 0
    
    # Sort by start time
    intervals.sort(key=lambda x: x[0])
    
    # Min-heap: stores end times of rooms
    rooms = []
    heapq.heappush(rooms, intervals[0][1])
    
    for i in range(1, len(intervals)):
        start, end = intervals[i]
        
        # If the earliest-ending room is free, reuse it
        if rooms[0] <= start:
            heapq.heappop(rooms)
        
        # Assign a room (new or reused)
        heapq.heappush(rooms, end)
    
    return len(rooms)


# Examples
intervals = [[0, 30], [5, 10], [15, 20]]
print(minMeetingRooms(intervals))  # 2

intervals2 = [[7, 10], [2, 4]]
print(minMeetingRooms(intervals2))  # 1

Approach: After sorting by start time, for each meeting check whether "the earliest-ending room" can be reused. The min-heap lets us find the earliest-ending room in O(log n). The final heap size is the minimum number of rooms needed.

12.20 Heap vs Sort vs Quickselect: Three Approaches to Top-K

How to choose?

1. K close to n (e.g., K > n/2): Just sort — simplest
2. K small and data is streaming (cannot fit all in memory): Heap is the only option
3. K small and data supports random access: Quickselect is fastest on average
4. Need sorted output with small K: Heap + sort the heap result
5. Need worst-case guarantee: Heap (Quickselect is O(n²) worst case, unless using median-of-medians)

import heapq
import random

def quickselect(nums, k):
    """Quickselect: find the kth largest element, average O(n)"""
    target = len(nums) - k  # convert to target-th smallest
    
    def select(left, right):
        pivot_idx = random.randint(left, right)
        nums[pivot_idx], nums[right] = nums[right], nums[pivot_idx]
        pivot = nums[right]
        
        store = left
        for i in range(left, right):
            if nums[i] < pivot:
                nums[i], nums[store] = nums[store], nums[i]
                store += 1
        nums[store], nums[right] = nums[right], nums[store]
        
        if store == target:
            return nums[store]
        elif store < target:
            return select(store + 1, right)
        else:
            return select(left, store - 1)
    
    return select(0, len(nums) - 1)


# Comparing three methods
nums = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
k = 3

# Method 1: Sort
sorted_result = sorted(nums, reverse=True)[:k]
print(f"Sort: {sorted_result}")      # [9, 6, 5]

# Method 2: Heap
heap_result = heapq.nlargest(k, nums)
print(f"Heap: {heap_result}")        # [9, 6, 5]

# Method 3: Quickselect (finds kth largest only, no sorting)
kth = quickselect(nums[:], k)  # pass copy since it modifies the array
print(f"Quickselect kth={k}: {kth}")  # 5

12.21 When to Use Heaps vs Ordered Containers

Use heap (heapq) when:

• You only need to repeatedly extract min/max
• Data arrives in a stream
• You don't need arbitrary-key deletion
• Memory-sensitive (heaps are much more compact than BSTs)

Use ordered containers (e.g., sortedcontainers.SortedList) when:

• You need deletion at arbitrary positions
• You need range queries ("how many values between a and b?")
• You need rank-based access ("what is the kth smallest?")
• You need predecessor/successor queries

# Things heapq cannot do efficiently:
# 1. Delete a specific element (only lazy deletion)
# 2. Find "the 3rd smallest element" (must pop 3 times)
# 3. Modify priority of existing element (decrease-key)

# sortedcontainers can do these:
from sortedcontainers import SortedList

sl = SortedList([5, 3, 8, 1, 2])
sl.remove(3)        # O(log n) remove by value
print(sl[2])        # O(log n) access by index → 5
sl.add(4)           # O(log n) insert
print(sl.bisect_left(4))  # O(log n) binary search for position

Rule of thumb: If you only need "fast extremum retrieval," use heapq. If you need richer query capabilities, use SortedList. If you are writing LeetCode and need an ordered container without importing third-party libraries, you can use a hand-written BST or simulate with two heaps.

12.22 Practical Advice

1. In Python interviews, heapq is your go-to tool. 90% of heap problems can be solved with heapq — no need to implement from scratch.

2. Signal words that indicate "use a heap":

   • "Top K..."
   • "Kth largest/smallest..."
   • "Median/extremum in dynamic data..."
   • "Merge multiple sorted..."
   • "Shortest path..." (Dijkstra)
   • "Greedily select the optimal..."

3. heapq complexity cheat sheet:

   • push/pop: O(log n)
   • heapify: O(n)
   • nlargest/nsmallest: O(n log k) or O(n + k log n)

4. Tuple trick: Using (priority, counter, data) as heap elements solves all comparison issues.

5. Don't overuse heaps: If total data size is small (< 1000), just sorting is usually simpler and fast enough. Heaps shine when data is large and K << n.

Chapter Summary

The heap is a concise yet powerful data structure. Its core insight is: if you only care about the extremum, you don't need to maintain a complete ordering. Using the structural constraint of a complete binary tree plus a weakened ordering (only parent-child relationships), heaps achieve O(1) extremum access and O(log n) modification on an array.

From an engineering perspective, the heap's array implementation is the most cache-friendly tree structure — no pointers, no fragmentation, contiguous memory. This is the fundamental reason it often outperforms theoretically superior but pointer-heavy schemes (like Fibonacci heaps) in practice.

In the next chapter, we will study hash tables — another design philosophy that trades "weak constraints" for "high performance." Hash tables abandon all ordering information, pursuing only O(1) exact lookup.