Algorithm Templates: Heap

Welcome to the Heap templates page! Here you’ll find battle-tested Python snippets for every common heap (priority queue) pattern on LeetCode — from basic min/max heaps to advanced techniques like K-way merge, Two Heaps for medians, and Dijkstra’s shortest path. Each section is self-contained so you can copy-paste directly into your solutions. See also Data Structures for related patterns.

New to Heaps? A heap (priority queue) always gives you the smallest (min-heap) or largest (max-heap) element in O(1). Think of it as a self-sorting container. Whenever a problem says “k largest”, “k smallest”, “median”, or “merge sorted lists”, think heap.

Contents

• Heap Overview
• Min Heap
• Max Heap
• Custom Comparators
• Common Patterns
• K-way Merge
• Top K Elements
• Two Heaps
• Dijkstra’s Algorithm

Heap Overview

A heap (priority queue) is a complete binary tree that satisfies the heap property:

• Min Heap: Parent node is always less than or equal to its children
• Max Heap: Parent node is always greater than or equal to its children

In C++, priority_queue is a max-heap by default. To get a min-heap, pass greater<int> as the comparator.

Key Operations:

Operation	What it does	Time
push(x)	Insert element	O(log n)
pop()	Remove top element	O(log n)
top()	Access top element (min or max)	O(1)
empty()	Check if empty	O(1)
size()	Get number of elements	O(1)

Use Cases:

• Finding K largest/smallest elements
• Merging K sorted sequences
• Maintaining running median
• Shortest path algorithms (Dijkstra’s)
• Scheduling problems (meeting rooms, task ordering)
• Stream processing (continuously arriving data)

How a Min-Heap Works (Visualization)

Min Heap

When to use: You need the smallest element quickly — “k largest elements” (use min-heap of size k), sorting streams, or Dijkstra’s algorithm.

Min heap keeps the smallest element at the top.

import heapq

# Min heap in Python (heapq is min-heap by default)
min_heap = []
heapq.heappush(min_heap, 5)
heapq.heappush(min_heap, 2)
heapq.heappush(min_heap, 8)
heapq.heappush(min_heap, 1)

smallest = min_heap[0]         # 1
removed = heapq.heappop(min_heap)  # removes 1
next_smallest = min_heap[0]    # 2

Example: Find K Smallest Elements

import heapq

class Solution:
    def findKSmallest(self, nums, k):
        minHeap = []

        for num in nums:
            heapq.heappush(minHeap, num)

        result = []

        for i in range(k):
            if minHeap:
                result.append(heapq.heappop(minHeap))

        return result

Max Heap

When to use: You need the largest element quickly — “k smallest elements” (use max-heap of size k), greedy scheduling, or “last stone weight” style problems.

Max heap keeps the largest element at the top (default in C++).

import heapq

# Max heap via negation
max_heap = []
heapq.heappush(max_heap, -5)
heapq.heappush(max_heap, -2)
heapq.heappush(max_heap, -8)
heapq.heappush(max_heap, -1)

largest = -max_heap[0]         # 8
removed = -heapq.heappop(max_heap)  # removes 8
next_largest = -max_heap[0]    # 5

Example: Find K Largest Elements

import heapq

class Solution:
    def findKLargest(self, nums, k):
        maxHeap = []

        for num in nums:
            heapq.heappush(maxHeap, -num)  # simulate max heap

        result = []

        for i in range(k):
            if maxHeap:
                result.append(-heapq.heappop(maxHeap))

        return result

Custom Comparators

When to use: The heap elements are structs, pairs, or tuples and you need to order by a specific field (e.g., sort by cost, frequency, or distance).

Using Struct

import heapq

# Custom comparator for pairs: min heap by second element
# (Python uses tuple ordering instead of struct comparator)
pq = []

# Example: :value, frequency - keep element with smallest frequency on top
heapq.heappush(pq, (5, 1))
heapq.heappush(pq, (3, 2))
heapq.heappush(pq, (7, 3))

print(pq[0])  # (3, 2)

import heapq

# Custom struct with comparator: min heap by cost
class Node:
    def __init__(self, cost, node_id):
        self.cost = cost
        self.node_id = node_id

    def __lt__(self, other):
        return self.cost < other.cost  # Min heap by cost

pq = []

# Example usage
heapq.heappush(pq, Node(10, 1))  # cost 10, id 1
heapq.heappush(pq, Node(5, 2))   # cost 5, id 2
heapq.heappush(pq, Node(15, 3))  # cost 15, id 3

print(pq[0].cost)  # 5

Using Lambda

import heapq

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def dist2(self):
        return self.x * self.x + self.y * self.y

    def __lt__(self, other):
        return self.dist2() < other.dist2()  # min heap by squared distance

pq = []
heapq.heappush(pq, Point(3, 4))  # dist2 = 25
heapq.heappush(pq, Point(1, 1))  # dist2 = 2
closest = heapq.heappop(pq)

Custom Object Comparator

# Keep K largest elements
import heapq

min_heap = []  # min heap to keep K largest
for num in nums:
    heapq.heappush(min_heap, num)
    if len(min_heap) > k:
        heapq.heappop(min_heap)  # remove smallest
# now min_heap contains K largest elements

Common Patterns

Pattern 1: Maintain K Elements

Keep only K elements in heap, remove smallest/largest when size exceeds K.

# Top K frequent elements
import heapq
from collections import Counter

freq = Counter(nums)
min_heap = []  # (frequency, element)
for num, count in freq.items():
    heapq.heappush(min_heap, (count, num))
    if len(min_heap) > k:
        heapq.heappop(min_heap)

Pattern 2: Frequency-Based

Use heap with frequency counts.

# Merge K sorted lists
import heapq

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


def merge_k_lists(lists):
    heap = []  # (value, list_index, node)

    for i, node in enumerate(lists):
        if node is not None:
            heapq.heappush(heap, (node.val, i, node))

    dummy = ListNode()
    cur = dummy
    while heap:
        _, i, node = heapq.heappop(heap)
        cur.next = node
        cur = cur.next
        if node.next is not None:
            heapq.heappush(heap, (node.next.val, i, node.next))

    return dummy.next

K-way Merge

When to use: The problem says “merge k sorted lists/arrays” or you need to produce a globally sorted sequence from multiple sorted sources.

Merge K sorted lists/arrays using a min heap.

# Merge K sorted arrays
import heapq

def merge_k_sorted_arrays(arrays):
    heap = []  # (value, array_index, position)
    for i, arr in enumerate(arrays):
        if arr:
            heapq.heappush(heap, (arr[0], i, 0))

    result = []
    while heap:
        val, arr_idx, pos = heapq.heappop(heap)
        result.append(val)
        nxt = pos + 1
        if nxt < len(arrays[arr_idx]):
            heapq.heappush(heap, (arrays[arr_idx][nxt], arr_idx, nxt))
    return result

K-way Merge for Arrays

def topKFrequent(self, nums, k):
    import heapq
    from collections import Counter

    freq = Counter(nums)
    min_heap = []  # (count, num)

    for num, count in freq.items():
        heapq.heappush(min_heap, (count, num))
        if len(min_heap) > k:
            heapq.heappop(min_heap)

    return [num for count, num in min_heap]

Top K Elements

When to use: The problem asks for “kth largest”, “top k frequent”, “k closest” — maintain a heap of size k and evict the least relevant element.

Top K Frequent Elements

def kClosest(self, points, k):
    import heapq

    max_heap = []  # (-dist2, x, y)
    for x, y in points:
        dist2 = x * x + y * y
        heapq.heappush(max_heap, (-dist2, x, y))
        if len(max_heap) > k:
            heapq.heappop(max_heap)

    return [[x, y] for _, x, y in max_heap]

K Closest Points to Origin

class Solution:
    def findKthLargest(self, nums, k):
        import heapq

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

Kth Largest Element in an Array (LC 215)

Solution 1: Min Heap (O(n log k))

Keep a min heap of size k. The top element will be the kth largest.

class Solution:
    def findKthLargest(self, nums, k):
        target = len(nums) - k
        left, right = 0, len(nums) - 1

        while True:
            pivot_index = self.partition(nums, left, right)
            if pivot_index == target:
                return nums[pivot_index]
            if pivot_index < target:
                left = pivot_index + 1
            else:
                right = pivot_index - 1

    def partition(self, nums, left, right):
        pivot = nums[right]
        i = left
        for j in range(left, right):
            if nums[j] <= pivot:
                nums[i], nums[j] = nums[j], nums[i]
                i += 1
        nums[i], nums[right] = nums[right], nums[i]
        return i

Solution 2: QuickSelect (O(n) average, O(n²) worst case)

Use partition-based selection algorithm.

class MedianFinder:
    def __init__(self):
        import heapq
        self._heapq = heapq
        self.max_heap = []  # lower half as negative values
        self.min_heap = []  # upper half

    def addNum(self, num):
        self._heapq.heappush(self.max_heap, -num)
        self._heapq.heappush(self.min_heap, -self._heapq.heappop(self.max_heap))
        if len(self.max_heap) < len(self.min_heap):
            self._heapq.heappush(self.max_heap, -self._heapq.heappop(self.min_heap))

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

Comparison:

• Heap: O(n log k) time, O(k) space - Simple and efficient for small k
• QuickSelect: O(n) average time, O(n²) worst case, O(1) space - Better for large k

Two Heaps

When to use: The problem mentions “median”, “sliding median”, or requires tracking the middle value of a dynamic stream. Use a max-heap for the lower half and a min-heap for the upper half.

Maintain two heaps to find median or balance elements.

Find Median from Data Stream

def medianSlidingWindow(self, nums, k):
    # Reference implementation using sorted window (O(n * k))
    import bisect

    window = sorted(nums[:k])
    medians = []

    for i in range(k, len(nums) + 1):
        if k % 2 == 1:
            medians.append(float(window[k // 2]))
        else:
            medians.append((window[k // 2 - 1] + window[k // 2]) / 2.0)

        if i == len(nums):
            break

        out_num = nums[i - k]
        in_num = nums[i]
        window.pop(bisect.bisect_left(window, out_num))
        bisect.insort(window, in_num)

    return medians

Sliding Window Median

# Shortest path from source to all nodes
import heapq

def dijkstra(graph, start):
    # graph[u] = [(v, weight), ...]
    n = len(graph)
    dist = [float("inf")] * n
    dist[start] = 0

    pq = [(0, start)]  # (distance, node)
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        for v, weight in graph[u]:
            new_dist = d + weight
            if new_dist < dist[v]:
                dist[v] = new_dist
                heapq.heappush(pq, (new_dist, v))
    return dist

Dijkstra’s Algorithm

When to use: The problem asks for “shortest path”, “minimum cost path”, or “cheapest route” in a weighted graph with non-negative edges.

Use min heap for shortest path finding.

import heapq


# Shortest path from source to all nodes
def dijkstra(graph: list[list[tuple[int, int]]], start: int) -> list[int]:
    n = len(graph)
    dist = [10**18] * n
    dist[start] = 0

    # Min heap: (distance, node)
    pq = [(0, start)]

    while pq:
        d, u = heapq.heappop(pq)

        if d > dist[u]:  # Already processed with better distance
            continue

        for v, weight in graph[u]:
            newDist = dist[u] + weight
            if newDist < dist[v]:
                dist[v] = newDist
                heapq.heappush(pq, (newDist, v))

    return dist

Easy Problems

ID	Title	Link	Solution
703	Kth Largest Element in a Stream	Link	-
1046	Last Stone Weight	Link	-
1167	Minimum Cost to Connect Sticks	Link	-

Medium Problems

ID	Title	Link	Solution
23	Merge k Sorted Lists	Link	Solution
215	Kth Largest Element in an Array	Link	Solution
253	Meeting Rooms II	Link	Solution
295	Find Median from Data Stream	Link	-
347	Top K Frequent Elements	Link	Solution
378	Kth Smallest Element in a Sorted Matrix	Link	-
692	Top K Frequent Words	Link	Solution
621	Task Scheduler	Link	-
767	Reorganize String	Link	-
973	K Closest Points to Origin	Link	Solution
1976	Number of Ways to Arrive at Destination	Link	Solution
2406	Divide Intervals Into Minimum Number of Groups	Link	Solution
1353	Maximum Number of Events That Can Be Attended	Link	Solution

Hard Problems

ID	Title	Link	Solution
239	Sliding Window Maximum	Link	Solution
480	Sliding Window Median	Link	Solution
743	Network Delay Time	Link	-
787	Cheapest Flights Within K Stops	Link	-
871	Minimum Number of Refueling Stops	Link	-

Common Heap Patterns

Pattern 1: K Largest/Smallest

• Use min heap to keep K largest (remove smallest when size > K)
• Use max heap to keep K smallest (remove largest when size > K)

Pattern 2: Frequency-Based

• Count frequencies, use heap to find top K by frequency

Pattern 3: K-way Merge

• Push first element of each sequence into min heap
• Pop smallest, push next element from same sequence

Pattern 4: Two Heaps

• Maintain two balanced heaps for median finding
• One heap for lower half, one for upper half

Pattern 5: Shortest Path

• Use min heap in Dijkstra’s algorithm
• Store {distance, node} pairs

Key Insights

1. Min Heap for K Largest: Keep K largest by removing smallest
2. Max Heap for K Smallest: Keep K smallest by removing largest
3. Custom Comparators: Use lambda or struct for complex ordering
4. Two Heaps: Balance two heaps for median problems
5. Efficiency: Heap operations are O(log n), making it efficient for dynamic problems

Time Complexity

Operation	Time Complexity
push()	O(log n)
pop()	O(log n)
top()	O(1)
empty()	O(1)
size()	O(1)

Space Complexity

• Heap Storage: O(n) where n is number of elements
• Auxiliary Space: O(1) for operations (excluding storage)

When to Use Heap

1. K Largest/Smallest: Finding top K elements
2. K-way Merge: Merging K sorted sequences
3. Scheduling: Meeting rooms, task scheduling
4. Shortest Path: Dijkstra’s algorithm
5. Median Finding: Two heaps pattern
6. Frequency Problems: Top K frequent elements

Common Mistakes

1. Wrong Comparator: Using > instead of < (or vice versa) for min/max heap
2. Not Handling Empty: Accessing top() without checking empty()
3. Wrong Heap Type: Using max heap when min heap is needed
4. Not Maintaining Size: Forgetting to pop when size exceeds K
5. Custom Comparator Logic: Reversing the comparison logic incorrectly

Related Data Structures

• Set/Multiset: For maintaining sorted order with duplicates
• Map: For frequency counting before heap operations
• Deque: For sliding window problems (alternative to heap)

Summary Table

Pattern	Signal Phrases	Key Idea
Min Heap	“k largest”, “sort”	Keep smallest on top
Max Heap	“k smallest”	Keep largest on top
K-way Merge	“merge k sorted”	Push heads, pop smallest
Top K	“kth largest”, “top k frequent”	Heap of size k
Two Heaps	“median”, “sliding median”	Max-heap for lower half, min-heap for upper
Dijkstra	“shortest path”, “minimum cost”	Greedy + min-heap

More templates

• Beginner’s Guide: LeetCode Beginner’s Guide
• Data structures (heap, monotonic queue): Data Structures & Core Algorithms
• Graph (Dijkstra): Graph
• Master index: Categories & Templates