Heap & Priority Queue

Back to DSA & Algorithms/00 - Roadmap Overview

What is a Heap?

A heap is a special binary tree where the parent is always smaller (min-heap) or larger (max-heap) than its children. It's stored as an array for efficiency.

Min-Heap: Parent ≤ Children (smallest at top)

        1              Array: [1, 3, 5, 7, 4, 6]
       / \
      3   5            Parent of index i: (i-1) / 2
     / \  /            Left child: 2*i + 1
    7  4  6            Right child: 2*i + 2

Max-Heap: Parent ≥ Children (largest at top)

Why It's Stored as an Array

No pointers needed. Parent/child relationships are computed with index math. Cache-friendly.

Key Operations

Operation	Time	Description
`peek` / `top`	O(1)	Look at smallest/largest element
`push` / `insert`	O(log n)	Add element, bubble up to maintain order
`pop` / `extract`	O(log n)	Remove top, move last to top, bubble down
`heapify`	O(n)	Build heap from unsorted array (NOT O(n log n)!)

Priority Queue vs Heap

Priority Queue = abstract concept (process highest priority first). Heap = concrete implementation of a priority queue.

They're used interchangeably in interviews.

Java PriorityQueue Cheat Sheet

Java's PriorityQueue is a min-heap by default. For max-heap, pass a reverse comparator.

java
import java.util.*;

// Min-heap
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.offer(5);
minHeap.offer(2);
minHeap.offer(8);

minHeap.peek();   // Peek: 2 (smallest)
minHeap.poll();   // Poll: 2 (removes and returns smallest)
minHeap.peek();   // Now: 5

// Max-heap: use reverse comparator
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
maxHeap.offer(5);
maxHeap.offer(2);
maxHeap.offer(8);

maxHeap.peek();   // Peek: 8 (largest)
maxHeap.poll();   // Poll: 8

// Heapify: Pass a collection to the constructor — O(n)
List<Integer> nums = new ArrayList<>(Arrays.asList(5, 3, 8, 1, 2));
PriorityQueue<Integer> heap = new PriorityQueue<>(nums);
// heap is now a valid min-heap, peek() returns 1

// Custom comparator for complex objects:
// Compare by first element of int[], then by second, etc.
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> {
    if (a[0] != b[0]) return Integer.compare(a[0], b[0]);
    return Integer.compare(a[1], b[1]);
});
pq.offer(new int[]{priority, item});
// Tiebreaker: add a counter as the second field
pq.offer(new int[]{priority, counter, item});

Pattern 1: Top K Elements

What it is

Find the K largest (or smallest) elements efficiently.

The Key Insight

For "K largest": use a min-heap of size K. The heap always contains the K largest elements seen so far. When a new element is larger than the heap's smallest, swap them.

Why min-heap for K LARGEST? Counterintuitive but smart:
The min-heap's top is the SMALLEST of the K largest elements.
Anything smaller than the top can't possibly be in the top K.
So we only need to compare with the top — O(log K) per element.
Total: O(n log K) instead of O(n log n) for sorting.

Step-by-Step

java
// Problem: Find the Kth largest element
// Input: [3, 2, 1, 5, 6, 4], k = 2
// Output: 5

public int findKthLargest(int[] nums, int k) {
    // Build a min-heap of size k
    PriorityQueue<Integer> heap = new PriorityQueue<>();
    for (int i = 0; i < k; i++) {
        heap.offer(nums[i]);
    }

    for (int i = k; i < nums.length; i++) {
        if (nums[i] > heap.peek()) {        // Bigger than current kth largest?
            heap.poll();                     // Remove smallest
            heap.offer(nums[i]);             // Push new
        }
    }

    return heap.peek();  // Top of min-heap = kth largest
}

// Walkthrough: [3, 2, 1, 5, 6, 4], k=2
// heap = [2, 3] (built from first 2 elements)
// num=1: 1 < heap.peek()=2 -> skip
// num=5: 5 > heap.peek()=2 -> poll & offer -> heap=[3, 5]
// num=6: 6 > heap.peek()=3 -> poll & offer -> heap=[5, 6]
// num=4: 4 < heap.peek()=5 -> skip
// Answer: heap.peek() = 5

Top K Frequent Elements

java
public int[] topKFrequent(int[] nums, int k) {
    Map<Integer, Integer> count = new HashMap<>();
    for (int num : nums) {
        count.merge(num, 1, Integer::sum);
    }

    // Min-heap of (frequency, element), keep size k
    // Compare by frequency (value in the map)
    PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[0] - b[0]);
    for (Map.Entry<Integer, Integer> entry : count.entrySet()) {
        heap.offer(new int[]{entry.getValue(), entry.getKey()});
        if (heap.size() > k) {
            heap.poll();  // Remove lowest frequency
        }
    }

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

// Alternative: Bucket sort approach (O(n) time!)
public int[] topKFrequentBucket(int[] nums, int k) {
    Map<Integer, Integer> count = new HashMap<>();
    for (int num : nums) {
        count.merge(num, 1, Integer::sum);
    }
    // Bucket: index = frequency, value = list of numbers with that frequency
    @SuppressWarnings("unchecked")
    List<Integer>[] buckets = new List[nums.length + 1];
    for (int i = 0; i < buckets.length; i++) {
        buckets[i] = new ArrayList<>();
    }
    for (Map.Entry<Integer, Integer> entry : count.entrySet()) {
        buckets[entry.getValue()].add(entry.getKey());
    }

    List<Integer> result = new ArrayList<>();
    for (int i = buckets.length - 1; i > 0; i--) {  // High frequency first
        result.addAll(buckets[i]);
        if (result.size() >= k) {
            return result.subList(0, k).stream().mapToInt(Integer::intValue).toArray();
        }
    }
    return result.stream().mapToInt(Integer::intValue).toArray();
}

Problems

215. Kth Largest Element in an Array - Medium
347. Top K Frequent Elements - Medium
692. Top K Frequent Words - Medium
973. K Closest Points to Origin - Medium

Pattern 2: Merge K Sorted Lists/Arrays

What it is

Merge K sorted sequences into one sorted sequence. The heap tracks the smallest unprocessed element across all sequences.

The Mental Model

Imagine K conveyor belts, each carrying items in order. You want to pack items from all belts into one box, maintaining sorted order. You look at the front item of each belt, pick the smallest, and advance that belt.

java
public ListNode mergeKLists(ListNode[] lists) {
    // Compare by node value; use index as tiebreaker
    PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> {
        if (a[0] != b[0]) return a[0] - b[0];
        return a[1] - b[1];
    });
    // We need to track the actual nodes separately
    Map<Integer, ListNode> nodeMap = new HashMap<>();

    // Initialize: push first element from each list
    for (int i = 0; i < lists.length; i++) {
        if (lists[i] != null) {
            heap.offer(new int[]{lists[i].val, i});
            nodeMap.put(i, lists[i]);
            // (value, list_index)
            // list_index breaks ties (avoid comparing nodes)
        }
    }

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

    while (!heap.isEmpty()) {
        int[] top = heap.poll();           // Get smallest overall
        int val = top[0];
        int i = top[1];
        ListNode node = nodeMap.get(i);

        curr.next = node;
        curr = curr.next;

        if (node.next != null) {
            nodeMap.put(i, node.next);
            heap.offer(new int[]{node.next.val, i});
        }
    }

    return dummy.next;
}

// Time: O(N log K) where N = total elements, K = number of lists
// Space: O(K) for the heap

Problems

23. Merge k Sorted Lists - Hard
378. Kth Smallest Element in a Sorted Matrix - Medium

Pattern 3: Two Heaps (Finding Median)

What it is

Split elements into two halves using two heaps:

Max-heap for the lower half (quickly get the largest of the small numbers)
Min-heap for the upper half (quickly get the smallest of the large numbers)

The median is always at the top of one or both heaps.

The Mental Model

Two piles of sorted cards. Left pile (face up, highest visible) and right pile (face up, lowest visible). The median is between the two visible cards.

Lower half (max-heap):    Upper half (min-heap):
    [1, 2, 3]                [4, 5, 6]
         ↑                    ↑
     top = 3               top = 4
     
Median = (3 + 4) / 2 = 3.5

Step-by-Step

java
class MedianFinder {
    private PriorityQueue<Integer> lo;  // Max-heap — stores lower half
    private PriorityQueue<Integer> hi;  // Min-heap — stores upper half

    public MedianFinder() {
        lo = new PriorityQueue<>(Collections.reverseOrder());
        hi = new PriorityQueue<>();
    }

    public void addNum(int num) {
        // Step 1: Always add to max-heap first
        lo.offer(num);

        // Step 2: Balance — ensure max of lo <= min of hi
        hi.offer(lo.poll());

        // Step 3: Ensure lo has >= elements than hi
        if (hi.size() > lo.size()) {
            lo.offer(hi.poll());
        }
    }

    public double findMedian() {
        if (lo.size() > hi.size()) {
            return lo.peek();                                  // Odd count
        }
        return (lo.peek() + hi.peek()) / 2.0;                 // Even count
    }
}

// Walkthrough: Add 1, 2, 3
// Add 1: lo=[1], hi=[] -> push to hi -> lo=[], hi=[1] -> rebalance -> lo=[1], hi=[]
// Add 2: lo=[2,1], hi=[] -> push to hi -> lo=[1], hi=[2] -> balanced
//   Median: (1 + 2) / 2.0 = 1.5
// Add 3: lo=[3,1], hi=[2] -> push to hi -> lo=[1], hi=[2,3] -> rebalance -> lo=[2,1], hi=[3]
//   Median: lo.peek() = 2

// The invariants:
// 1. lo.size() == hi.size() or lo.size() == hi.size() + 1
// 2. max(lo) <= min(hi)  (all elements in lo <= all elements in hi)

Problems

295. Find Median from Data Stream - Hard
480. Sliding Window Median - Hard

Pattern 4: Scheduling / Greedy with Heap

Task Scheduler

java
public int leastInterval(char[] tasks, int n) {
    // Count frequency of each task
    Map<Character, Integer> counts = new HashMap<>();
    for (char task : tasks) {
        counts.merge(task, 1, Integer::sum);
    }
    // Max-heap of frequencies (most frequent first)
    PriorityQueue<Integer> heap = new PriorityQueue<>(Collections.reverseOrder());
    heap.addAll(counts.values());

    int time = 0;
    Deque<int[]> cooldown = new ArrayDeque<>();  // {remaining_count, time_available}

    while (!heap.isEmpty() || !cooldown.isEmpty()) {
        time++;

        if (!heap.isEmpty()) {
            int cnt = heap.poll() - 1;       // Decrement count
            if (cnt != 0) {
                cooldown.offer(new int[]{cnt, time + n});  // Available after cooldown
            }
        }

        if (!cooldown.isEmpty() && cooldown.peek()[1] == time) {
            heap.offer(cooldown.poll()[0]);
        }
    }

    return time;
}

// The greedy insight: Always process the most frequent task first.
// This minimizes idle time because the most frequent task creates
// the most waiting periods.

Problems

Things You MUST Be Aware Of

1. Java's PriorityQueue is Min-Heap by Default

java
// For max-heap, pass a reverse comparator:
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
maxHeap.offer(val);
int maxVal = maxHeap.poll();

// For custom objects, use a comparator:
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> {
    if (a[0] != b[0]) return Integer.compare(a[0], b[0]);
    return Integer.compare(a[1], b[1]);
});

2. Comparator Pitfalls

java
// Using (a, b) -> a - b can overflow for large values!
// SAFE: use Integer.compare(a, b) instead of a - b
PriorityQueue<Integer> pq = new PriorityQueue<>(Integer::compareTo);

// GOTCHA: If you store objects that aren't Comparable and don't provide a
// comparator, you'll get a ClassCastException at runtime.
// Fix: Always provide a Comparator for non-Comparable types.
int counter = 0;
PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> {
    if (a[0] != b[0]) return a[0] - b[0];  // priority
    return a[1] - b[1];                     // tiebreaker (counter)
});
heap.offer(new int[]{5, counter++, /* actual data */ 3});

3. Heap ≠ Sorted Array

java
// peek() is the min, but other elements are NOT sorted!
// A valid min-heap [1, 3, 2, 7, 5] is not sorted
// Only guarantee: parent <= children

// To get sorted order: poll all elements one by one
List<Integer> sorted = new ArrayList<>();
while (!heap.isEmpty()) {
    sorted.add(heap.poll());
}

4. Building a PriorityQueue from a Collection is O(n), Not O(n log n)

java
// Common mistake: thinking the constructor just "inserts n items"
// The math works out to O(n) due to the structure of the tree
// Most elements are at the bottom (many) but need very few swaps
List<Integer> list = Arrays.asList(5, 3, 8, 1, 2);
PriorityQueue<Integer> heap = new PriorityQueue<>(list);  // O(n)

5. QuickSelect Alternative

java
// For Kth largest/smallest, QuickSelect gives O(n) AVERAGE time
// But O(n^2) worst case. Heap gives O(n log k) guaranteed.
// Know both approaches — interviewer might ask for trade-offs.

Decision Guide

"K largest / K smallest / Kth element"
  └── Heap of size K (or QuickSelect for average O(n))

"Merge K sorted sequences"
  └── Min-heap with one element from each sequence

"Running median / streaming percentile"
  └── Two heaps (max-heap for low half, min-heap for high half)

"Process tasks by priority / frequency"
  └── Max-heap by frequency + cooldown queue

"Continuously get min/max from dynamic data"
  └── Heap (insert O(log n), get min O(1))