Heap / Priority Queue Pattern | CodeTutor

Heap / Priority Queue

Intermediate

17 questions using this pattern

What is Heap / Priority Queue?

A data structure that efficiently maintains the minimum or maximum element, supporting O(log n) insertion and extraction. Heaps are essential when you repeatedly need to access the smallest or largest element from a changing set.

Think of it like this...

Imagine a hospital emergency room where patients are treated by urgency, not arrival time. A priority queue (heap) lets you always know who's next without sorting everyone whenever someone new arrives. The most urgent patient "bubbles up" to the front automatically.

Another analogy: a to-do list that always shows your most important task first. When you add or complete tasks, the list reorganizes itself so the highest priority is always accessible in O(1) time.

Core Concept

A heap is a complete binary tree where each parent is smaller (min-heap) or larger (max-heap) than its children. This property guarantees:

Peek min/max: O(1) — it's always at the root
Insert: O(log n) — bubble up to maintain heap property
Extract min/max: O(log n) — remove root, bubble down to reheapify

Key insight: heaps don't fully sort the data. They only guarantee the root is the min/max. This partial ordering is enough for many problems and is more efficient than maintaining full sorted order.

When to use heaps:

Need repeated access to min/max element
Data changes frequently (insertions/deletions)
Full sorting is overkill (only need top K, not all elements sorted)

Kth Largest Element (Min-Heap)

Heap

import heapq

def find_kth_largest(nums: list[int], k: int) -> int:

    heap = []

    for num in nums:

        heapq.heappush(heap, num)  # Add element

        if len(heap) > k:

            heapq.heappop(heap)    # Remove smallest

    return heap[0]  # Root = kth largest

Variables

k=2

Input Array

Min-Heap (k=2) (size ≤ 2)

Problem

Find the 2nd largest element in [3, 2, 1, 5, 6, 4]. Sorting gives [1, 2, 3, 4, 5, 6], so 2nd largest is 5. But can we do better than O(n log n)?

1/33

Visual Walkthrough

Min-Heap Structure:

Array: [1, 3, 2, 7, 6, 4, 5]

As tree:
       1          (index 0)
      / \
     3   2        (indices 1, 2)
    / \ / \
   7  6 4  5      (indices 3, 4, 5, 6)

Parent of index i: (i-1) // 2
Left child: 2*i + 1
Right child: 2*i + 2

Inserting 0 into heap:

Add 0 at end:
       1
      / \
     3   2
    / \ / \
   7  6 4  5
  /
 0

Bubble up (0 < 7, swap):
       1
      / \
     3   2
    / \ / \
   0  6 4  5
  /
 7

Bubble up (0 < 3, swap):
       1
      / \
     0   2
    / \ / \
   3  6 4  5
  /
 7

Bubble up (0 < 1, swap):
       0
      / \
     1   2
    / \ / \
   3  6 4  5
  /
 7

Top K Elements using Min-Heap:

Find 3 largest from [3, 1, 4, 1, 5, 9, 2, 6]

Maintain min-heap of size 3:

Process 3: heap = [3]
Process 1: heap = [1, 3]
Process 4: heap = [1, 3, 4]
Process 1: 1 <= heap[0]=1, skip
Process 5: 5 > 1, remove 1, add 5 → heap = [3, 5, 4]
Process 9: 9 > 3, remove 3, add 9 → heap = [4, 5, 9]
Process 2: 2 <= 4, skip
Process 6: 6 > 4, remove 4, add 6 → heap = [5, 9, 6]

Result: [5, 6, 9] are the top 3

Code Template

Use this skeleton as a starting point for problems using this pattern:

python

import heapq

def find_k_largest(nums: list[int], k: int) -> list[int]:
    """Find k largest elements using min-heap."""
    # Min-heap of size k keeps k largest
    heap = []

    for num in nums:
        if len(heap) < k:
            heapq.heappush(heap, num)
        elif num > heap[0]:
            heapq.heapreplace(heap, num)  # Pop min, push new

    return heap


def find_k_smallest(nums: list[int], k: int) -> list[int]:
    """Find k smallest elements using max-heap (negated values)."""
    # Max-heap (negated) of size k keeps k smallest
    heap = []

    for num in nums:
        if len(heap) < k:
            heapq.heappush(heap, -num)
        elif num < -heap[0]:
            heapq.heapreplace(heap, -num)

    return [-x for x in heap]


def merge_k_sorted_lists(lists: list[list[int]]) -> list[int]:
    """Merge k sorted lists using min-heap."""
    heap = []
    result = []

    # Initialize heap with first element from each list
    for i, lst in enumerate(lists):
        if lst:
            heapq.heappush(heap, (lst[0], i, 0))

    while heap:
        val, list_idx, elem_idx = heapq.heappop(heap)
        result.append(val)

        # Add next element from same list
        if elem_idx + 1 < len(lists[list_idx]):
            next_val = lists[list_idx][elem_idx + 1]
            heapq.heappush(heap, (next_val, list_idx, elem_idx + 1))

    return result


class MedianFinder:
    """Find median from data stream using two heaps."""

    def __init__(self):
        self.small = []  # Max-heap (negated) for smaller half
        self.large = []  # Min-heap for larger half

    def add_num(self, num: int) -> None:
        # Add to max-heap (smaller half)
        heapq.heappush(self.small, -num)

        # Balance: largest of small should be <= smallest of large
        if self.large and -self.small[0] > self.large[0]:
            heapq.heappush(self.large, -heapq.heappop(self.small))

        # Size balance: small can have at most 1 more element
        if len(self.small) > len(self.large) + 1:
            heapq.heappush(self.large, -heapq.heappop(self.small))
        elif len(self.large) > len(self.small):
            heapq.heappush(self.small, -heapq.heappop(self.large))

    def find_median(self) -> float:
        if len(self.small) > len(self.large):
            return -self.small[0]
        return (-self.small[0] + self.large[0]) / 2


def kth_smallest_in_matrix(matrix: list[list[int]], k: int) -> int:
    """Find kth smallest in row-wise and column-wise sorted matrix."""
    n = len(matrix)
    heap = [(matrix[0][0], 0, 0)]
    visited = {(0, 0)}

    for _ in range(k - 1):
        val, r, c = heapq.heappop(heap)

        # Add right neighbor
        if c + 1 < n and (r, c + 1) not in visited:
            visited.add((r, c + 1))
            heapq.heappush(heap, (matrix[r][c + 1], r, c + 1))

        # Add bottom neighbor
        if r + 1 < n and (r + 1, c) not in visited:
            visited.add((r + 1, c))
            heapq.heappush(heap, (matrix[r + 1][c], r + 1, c))

    return heap[0][0]

Recognition Signals

Look for these keywords and patterns in problem descriptions:

kth largestkth smallesttop kmerge sortedmedianpriorityscheduleDijkstrafrequencyclosest points

When to Use

Finding K largest/smallest elements
K-way merge of sorted lists
Finding median from data stream
Task scheduling by priority
Dijkstra's shortest path algorithm

Common Mistakes

Using max-heap when min-heap needed (or vice versa)

Python's heapq is a min-heap. Using it directly for "k largest" keeps k smallest instead.

Fix:

For max-heap behavior, negate values:

heapq.heappush(heap, -num)  # Push negative
max_val = -heapq.heappop(heap)  # Negate back

Wrong heap size for "top K" problems

For "k largest," keeping a max-heap of all elements and extracting k times is O(n + k log n). Using min-heap of size k is O(n log k).

Fix:

For k largest: use min-heap of size k, remove smallest when full. For k smallest: use max-heap of size k, remove largest when full.

Pattern Variations

Top K elements

Keep k largest using min-heap of size k, or k smallest using max-heap of size k.

Examples: Kth Largest Element, Top K Frequent Elements

K-way merge

Merge k sorted lists efficiently by maintaining heap of current elements from each list.

Examples: Merge K Sorted Lists, Smallest Range Covering K Lists

Two heaps (median)

Maintain two heaps: max-heap for smaller half, min-heap for larger half. Median is at the roots.

Examples: Find Median from Data Stream, Sliding Window Median

Dijkstra's algorithm

Min-heap tracks vertices by shortest known distance. Extract minimum, relax edges, update heap.

Examples: Network Delay Time, Cheapest Flights Within K Stops

Task scheduling

Prioritize tasks by some criteria (deadline, duration). Process highest priority first.

Examples: Task Scheduler, Meeting Rooms III

Learning Path

1Warmup0/2

Start here to build foundational understanding.

Kth Largest Element in a StreamOptimal

#703Easy

Last Stone WeightOptimal

#1046Easy

2Core Practice0/10

Master the pattern with these representative problems.

Design TwitterOptimal

#355Medium

Hand of Straights

#846Medium

K Closest Points to OriginOptimal

#973Medium

Kth Largest Element in an ArrayOptimal

#215Medium

Longest Happy String

#1405Medium

Min Cost to Connect All PointsOptimal

#1584Medium

Network Delay TimeOptimal

#743Medium

Path With Minimum EffortOptimal

#1631Medium

Reorganize StringOptimal

#767Medium

Task Scheduler

#621Medium

3Challenge0/5

Test your mastery with complex variations.

Find Median from Data StreamOptimal

#295Hard

IPO

#502Hard

Merge k Sorted ListsOptimal

#23Hard

Minimum Interval to Include Each QueryOptimal

#1851Hard

Swim in Rising WaterOptimal

#778Hard

Related Patterns

Explore similar techniques:

Two Pointers

Use two pointers to traverse data from different positions, often moving toward or away from each other. This technique transforms O(n²) brute force into O(n) by eliminating redundant comparisons.

Binary Search

Efficiently search sorted data by repeatedly dividing the search space in half. This transforms O(n) linear search into O(log n) by eliminating half the remaining possibilities with each comparison.

When heap contains tuples, Python compares by first element, then second, etc. If first elements are equal, comparison moves to second element.

Fix:

Put the comparison key first in the tuple:

heapq.heappush(heap, (priority, item))

If items aren't comparable, use a counter as tiebreaker.