Heap / Priority Queue Pattern

Overview

Binary heap maintains min or max element at root, enabling O(log n) insert/delete and O(1) access to extreme element. Essential for scheduling, top-K, and streaming problems.

When to Use

• Top K / Kth largest/smallest
• Merge K sorted lists/arrays
• Median of data stream
• Task scheduling with priority
• Dijkstra's shortest path
• Event-driven simulation
• Meeting rooms / intervals

Template Code

Basic PriorityQueue Usage

// Min heap (default)
PriorityQueue<Integer> minHeap = new PriorityQueue<>();

// Max heap
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
// or
PriorityQueue<Integer> maxHeap2 = new PriorityQueue<>((a, b) -> b - a);

// Custom object heap
PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[0] - b[0]);

// Operations
heap.offer(element);      // O(log n)
heap.poll();              // O(log n)
heap.peek();              // O(1)
heap.size();              // O(1)
heap.isEmpty();           // O(1)

Kth Largest Element

public int findKthLargest(int[] nums, int k) {
    // Min heap of size k
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();

    for (int num : nums) {
        minHeap.offer(num);

        if (minHeap.size() > k) {
            minHeap.poll();  // Remove smallest
        }
    }

    return minHeap.peek();  // Kth largest
}

Top K Frequent Elements

public int[] topKFrequent(int[] nums, int k) {
    Map<Integer, Integer> freq = new HashMap<>();
    for (int num : nums) {
        freq.put(num, freq.getOrDefault(num, 0) + 1);
    }

    // Min heap by frequency
    PriorityQueue<Integer> minHeap = new PriorityQueue<>(
        (a, b) -> freq.get(a) - freq.get(b)
    );

    for (int num : freq.keySet()) {
        minHeap.offer(num);
        if (minHeap.size() > k) {
            minHeap.poll();
        }
    }

    int[] result = new int[k];
    for (int i = 0; i < k; i++) {
        result[i] = minHeap.poll();
    }
    return result;
}

Merge K Sorted Lists

public ListNode mergeKLists(ListNode[] lists) {
    PriorityQueue<ListNode> minHeap = new PriorityQueue<>(
        (a, b) -> a.val - b.val
    );

    // Add first node of each list
    for (ListNode list : lists) {
        if (list != null) {
            minHeap.offer(list);
        }
    }

    ListNode dummy = new ListNode(0);
    ListNode current = dummy;

    while (!minHeap.isEmpty()) {
        ListNode node = minHeap.poll();
        current.next = node;
        current = current.next;

        if (node.next != null) {
            minHeap.offer(node.next);
        }
    }

    return dummy.next;
}

Find Median from Data Stream

class MedianFinder {
    PriorityQueue<Integer> maxHeap;  // Left half (smaller elements)
    PriorityQueue<Integer> minHeap;  // Right half (larger elements)

    public MedianFinder() {
        maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        minHeap = new PriorityQueue<>();
    }

    public void addNum(int num) {
        maxHeap.offer(num);
        minHeap.offer(maxHeap.poll());

        // Balance: maxHeap can have at most 1 more element
        if (minHeap.size() > maxHeap.size()) {
            maxHeap.offer(minHeap.poll());
        }
    }

    public double findMedian() {
        if (maxHeap.size() > minHeap.size()) {
            return maxHeap.peek();
        }
        return (maxHeap.peek() + minHeap.peek()) / 2.0;
    }
}

K Closest Points to Origin

public int[][] kClosest(int[][] points, int k) {
    // Max heap by distance
    PriorityQueue<int[]> maxHeap = new PriorityQueue<>(
        (a, b) -> (b[0]*b[0] + b[1]*b[1]) - (a[0]*a[0] + a[1]*a[1])
    );

    for (int[] point : points) {
        maxHeap.offer(point);
        if (maxHeap.size() > k) {
            maxHeap.poll();
        }
    }

    return maxHeap.toArray(new int[k][]);
}

Meeting Rooms II

public int minMeetingRooms(int[][] intervals) {
    Arrays.sort(intervals, (a, b) -> a[0] - b[0]);  // Sort by start

    PriorityQueue<Integer> minHeap = new PriorityQueue<>();  // End times

    for (int[] interval : intervals) {
        if (!minHeap.isEmpty() && minHeap.peek() <= interval[0]) {
            minHeap.poll();  // Room freed up
        }
        minHeap.offer(interval[1]);  // Book room until end time
    }

    return minHeap.size();
}

Reorganize String

public String reorganizeString(String s) {
    int[] count = new int[26];
    for (char c : s.toCharArray()) {
        count[c - 'a']++;
    }

    PriorityQueue<int[]> maxHeap = new PriorityQueue<>(
        (a, b) -> b[1] - a[1]
    );

    for (int i = 0; i < 26; i++) {
        if (count[i] > 0) {
            maxHeap.offer(new int[]{i, count[i]});
        }
    }

    StringBuilder result = new StringBuilder();
    int[] prev = null;

    while (!maxHeap.isEmpty()) {
        int[] curr = maxHeap.poll();
        result.append((char)(curr[0] + 'a'));
        curr[1]--;

        if (prev != null && prev[1] > 0) {
            maxHeap.offer(prev);
        }
        prev = curr;
    }

    return result.length() == s.length() ? result.toString() : "";
}

Task Scheduler

public int leastInterval(char[] tasks, int n) {
    int[] count = new int[26];
    for (char task : tasks) {
        count[task - 'A']++;
    }

    PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
    for (int c : count) {
        if (c > 0) maxHeap.offer(c);
    }

    int cycles = 0;

    while (!maxHeap.isEmpty()) {
        List<Integer> temp = new ArrayList<>();

        // Process up to n+1 different tasks
        for (int i = 0; i <= n; i++) {
            if (!maxHeap.isEmpty()) {
                int remaining = maxHeap.poll() - 1;
                if (remaining > 0) {
                    temp.add(remaining);
                }
            }
            cycles++;

            // Break if no more tasks
            if (maxHeap.isEmpty() && temp.isEmpty()) {
                break;
            }
        }

        for (int t : temp) {
            maxHeap.offer(t);
        }
    }

    return cycles;
}

Smallest Range Covering K Lists

public int[] smallestRange(List<List<Integer>> nums) {
    // Min heap: [value, list index, element index]
    PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> a[0] - b[0]);

    int max = Integer.MIN_VALUE;

    // Add first element from each list
    for (int i = 0; i < nums.size(); i++) {
        int val = nums.get(i).get(0);
        minHeap.offer(new int[]{val, i, 0});
        max = Math.max(max, val);
    }

    int rangeStart = 0, rangeEnd = Integer.MAX_VALUE;

    while (minHeap.size() == nums.size()) {
        int[] curr = minHeap.poll();
        int min = curr[0], listIdx = curr[1], elemIdx = curr[2];

        // Update result if smaller range
        if (max - min < rangeEnd - rangeStart) {
            rangeStart = min;
            rangeEnd = max;
        }

        // Add next element from same list
        if (elemIdx + 1 < nums.get(listIdx).size()) {
            int nextVal = nums.get(listIdx).get(elemIdx + 1);
            minHeap.offer(new int[]{nextVal, listIdx, elemIdx + 1});
            max = Math.max(max, nextVal);
        }
    }

    return new int[]{rangeStart, rangeEnd};
}

IPO (Maximize Capital)

public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
    int n = profits.length;
    int[][] projects = new int[n][2];

    for (int i = 0; i < n; i++) {
        projects[i] = new int[]{capital[i], profits[i]};
    }

    Arrays.sort(projects, (a, b) -> a[0] - b[0]);  // Sort by capital

    PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
    int i = 0;

    for (int j = 0; j < k; j++) {
        // Add all affordable projects
        while (i < n && projects[i][0] <= w) {
            maxHeap.offer(projects[i][1]);
            i++;
        }

        if (maxHeap.isEmpty()) break;

        w += maxHeap.poll();  // Take most profitable
    }

    return w;
}

Time & Space Complexity

Operation	Time	Space
Insert (offer)	O(log n)	O(1)
Delete (poll)	O(log n)	O(1)
Peek	O(1)	O(1)
Build heap	O(n)	O(1)
Top K	O(n log k)	O(k)
Merge K lists	O(n log k)	O(k)

Common Interview Questions

1. Kth Largest Element - Min heap of size k
2. Top K Frequent Elements - Frequency + min heap
3. Merge K Sorted Lists - Min heap of k nodes
4. Find Median from Data Stream - Two heaps
5. K Closest Points to Origin - Max heap of size k
6. Meeting Rooms II - Min heap of end times
7. Reorganize String - Max heap + previous tracking
8. Task Scheduler - Max heap + cooling period
9. Smallest Range Covering K Lists - Track min/max
10. Ugly Number II - Min heap for generation
11. IPO - Two heaps (capital + profit)
12. Sliding Window Median - Two heaps + lazy removal
13. K Pairs with Smallest Sums - Min heap exploration
14. Trapping Rain Water II - 2D min heap BFS

Tips & Tricks

• For "K largest", use min heap of size K
• For "K smallest", use max heap of size K
• Two heaps pattern for median: maxHeap (left) + minHeap (right)
• When merging K lists, heap size is always K
• For streaming data, maintain heap as elements come in
• Custom comparators: return negative if a should come first
• Avoid Integer overflow in comparators: use Integer.compare()