Algorithm Templates: Heap

Welcome to the Heap templates page! Here you’ll find battle-tested Java 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.

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 |

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 Java, PriorityQueue is a min-heap by default. To get a min-heap, use the default constructor for a min-heap, or pass Comparator.reverseOrder() for max-heap as the comparator.

Key Operations:

Operation	What it does	Time
`offer(x)`	Insert element	O(log n)
`poll()`	Remove top element	O(log n)
`peek()`	Access top element (min or max)	O(1)
`isEmpty()`	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.

Example: Find K Smallest Elements

// Min heap (smallest element at top)
PriorityQueue<Integer> minHeap = new PriorityQueue<>();

// Basic operations
minHeap.offer(5);
minHeap.offer(2);
minHeap.offer(8);
minHeap.offer(1);

minHeap.peek();    // Returns 1 (smallest)
minHeap.poll();    // Removes 1
minHeap.peek();    // Returns 2 (next smallest)

Example: Find K Smallest Elements

int[] findKSmallest(int[] nums, int k) {
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    for (int num : nums) minHeap.offer(num);
    int[] result = new int[k];
    for (int i = 0; i < k && !minHeap.isEmpty(); i++) {
        result[i] = minHeap.poll();
    }
    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++).

Example: Find K Largest Elements

// Max heap (largest element at top)
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());

maxHeap.offer(5);
maxHeap.offer(2);
maxHeap.offer(8);
maxHeap.offer(1);

maxHeap.peek();    // Returns 8 (largest)
maxHeap.poll();    // Removes 8
maxHeap.peek();    // Returns 5 (next largest)

Example: Find K Largest Elements

int[] findKLargest(int[] nums, int k) {
    PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
    for (int num : nums) maxHeap.offer(num);
    int[] result = new int[k];
    for (int i = 0; i < k && !maxHeap.isEmpty(); i++) {
        result[i] = maxHeap.poll();
    }
    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

Using Lambda

Custom Object Comparator

// Min heap by second element (frequency)
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[1], b[1]));
pq.offer(new int[] {1, 5});
pq.offer(new int[] {2, 3});
pq.offer(new int[] {3, 7});
pq.peek(); // {2, 3}

Custom Object Comparator

record Node(int cost, int id) {}
PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingInt(n -> n.cost));
pq.offer(new Node(10, 1));
pq.offer(new Node(5, 2));
pq.peek(); // Node(5, 2)

Distance Comparator (Dijkstra)

PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
pq.offer(new int[] {10, 0});
pq.offer(new int[] {5, 1});
pq.peek(); // {5, 1}

Point Comparator

record Point(int x, int y) {
    int distSq() { return x * x + y * y; }
}
PriorityQueue<Point> pq = new PriorityQueue<>(Comparator.comparingInt(Point::distSq));

Common Patterns

Pattern 1: Maintain K Elements

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

Pattern 2: Frequency-Based

Use heap with frequency counts.

PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int num : nums) {
    minHeap.offer(num);
    if (minHeap.size() > k) minHeap.poll();
}

Pattern 2: Frequency-Based

Map<Integer, Integer> freq = new HashMap<>();
for (int num : nums) freq.put(num, freq.getOrDefault(num, 0) + 1);
PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
for (var e : freq.entrySet()) {
    minHeap.offer(new int[] {e.getValue(), e.getKey()});
    if (minHeap.size() > k) minHeap.poll();
}

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.

K-way Merge for Arrays

ListNode mergeKLists(ListNode[] lists) {
    PriorityQueue<ListNode> pq = new PriorityQueue<>(Comparator.comparingInt(n -> n.val));
    for (ListNode head : lists) if (head != null) pq.offer(head);
    ListNode dummy = new ListNode(0), cur = dummy;
    while (!pq.isEmpty()) {
        ListNode node = pq.poll();
        cur.next = node;
        cur = cur.next;
        if (node.next != null) pq.offer(node.next);
    }
    return dummy.next;
}

K-way Merge for Arrays

int[] mergeKSortedArrays(int[][] arrays) {
    record Entry(int val, int arrIdx, int pos) {}
    PriorityQueue<Entry> pq = new PriorityQueue<>(Comparator.comparingInt(e -> e.val));
    for (int i = 0; i < arrays.length; i++) {
        if (arrays[i].length > 0) pq.offer(new Entry(arrays[i][0], i, 0));
    }
    List<Integer> result = new ArrayList<>();
    while (!pq.isEmpty()) {
        Entry e = pq.poll();
        result.add(e.val);
        int next = e.pos + 1;
        if (next < arrays[e.arrIdx].length) {
            pq.offer(new Entry(arrays[e.arrIdx][next], e.arrIdx, next));
        }
    }
    return result.stream().mapToInt(Integer::intValue).toArray();
}

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

K Closest Points to Origin

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.

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

Use partition-based selection algorithm.

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

int[] topKFrequent(int[] nums, int k) {
    Map<Integer, Integer> freq = new HashMap<>();
    for (int num : nums) freq.put(num, freq.getOrDefault(num, 0) + 1);
    PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
    for (var e : freq.entrySet()) {
        minHeap.offer(new int[] {e.getValue(), e.getKey()});
        if (minHeap.size() > k) minHeap.poll();
    }
    int[] result = new int[k];
    for (int i = k - 1; i >= 0; i--) result[i] = minHeap.poll()[1];
    return result;
}

K Closest Points to Origin

int[][] kClosest(int[][] points, int k) {
    PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a, b) -> {
        int da = a[0] * a[0] + a[1] * a[1];
        int db = b[0] * b[0] + b[1] * b[1];
        return Integer.compare(db, da);
    });
    for (int[] p : points) {
        maxHeap.offer(p);
        if (maxHeap.size() > k) maxHeap.poll();
    }
    int[][] result = new int[k][2];
    for (int i = k - 1; i >= 0; i--) result[i] = maxHeap.poll();
    return result;
}

Kth Largest Element in an Array (LC 215)

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

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int num : nums) {
            minHeap.offer(num);
            if (minHeap.size() > k) minHeap.poll();
        }
        return minHeap.peek();
    }
}

Solution 2: QuickSelect (O(n) average)

class Solution {
    public int findKthLargest(int[] nums, int k) {
        return quickSelect = new return(nums, 0, nums.length - 1, nums.length - k);
    }

    private int quickSelect(int[] nums, int l, int r, int k) {
        if (l == r) return nums[k];
        int pivot = nums[l], i = l - 1, j = r + 1;
        while (i < j) {
            while (nums[++i] < pivot);
            while (nums[--j] > pivot);
            if (i < j) { int t = nums[i]; nums[i] = nums[j]; nums[j] = t; }
        }
        if (k <= j) return quickSelect = new return(nums, l, j, k);
        return quickSelect = new return(nums, j + 1, r, 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

Sliding Window Median

class MedianFinder {
    private final PriorityQueue<Integer> lo = new PriorityQueue<>(Comparator.reverseOrder());
    private final PriorityQueue<Integer> hi = new PriorityQueue<>();

    public void addNum(int num) {
        lo.offer(num);
        hi.offer(lo.poll());
        if (lo.size() < hi.size()) lo.offer(hi.poll());
    }

    public double findMedian() {
        return lo.size() > hi.size() ? lo.peek() : (lo.peek() + hi.peek()) / 2.0;
    }
}

Sliding Window Median

// Sliding window median (LC 480) typically uses two balanced heaps
// or a TreeMultiset-style structure. See the dedicated LC 480 post for a full solution.

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.

int[] dijkstra(List<List<int[]>> graph, int start) {
    int n = graph.size();
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[start] = 0;
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
    pq.offer(new int[] {0, start});
    while (!pq.isEmpty()) {
        int[] cur = pq.poll();
        int d = cur[0], u = cur[1];
        if (d > dist[u]) continue;
        for (int[] e : graph.get(u)) {
            int v = e[0], w = e[1];
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.offer(new int[] {dist[v], 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

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

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

Time Complexity

Space Complexity

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

When to Use Heap

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

Common Mistakes

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

Set/Multiset: For maintaining sorted order with duplicates
Map: For frequency counting before heap operations
Deque: For sliding window problems (alternative to 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

Summary Table

Contents

Heap Overview

How a Min-Heap Works (Visualization)

Min Heap

Example: Find K Smallest Elements

Example: Find K Smallest Elements

Max Heap

Example: Find K Largest Elements

Example: Find K Largest Elements

Custom Comparators

Using Struct

Using Lambda

Custom Object Comparator

Custom Object Comparator

Distance Comparator (Dijkstra)

Point Comparator

Common Patterns

Pattern 1: Maintain K Elements

Pattern 2: Frequency-Based

Pattern 2: Frequency-Based

K-way Merge

K-way Merge for Arrays

K-way Merge for Arrays

Top K Elements

Top K Frequent Elements

K Closest Points to Origin

Kth Largest Element in an Array (LC 215)

K Closest Points to Origin

Kth Largest Element in an Array (LC 215)

Two Heaps

Find Median from Data Stream

Sliding Window Median

Sliding Window Median

Dijkstra’s Algorithm

Easy Problems

Medium Problems

Hard Problems

Common Heap Patterns

Pattern 1: K Largest/Smallest

Pattern 2: Frequency-Based

Pattern 3: K-way Merge

Pattern 4: Two Heaps

Pattern 5: Shortest Path

Key Insights

Time Complexity

Space Complexity

When to Use Heap

Common Mistakes

Related Data Structures

More templates

Related Posts

Recent Posts