🏔️ Heap (Priority Queue)

Concept

A Heap is a complete binary tree satisfying the heap property:

• Min-Heap: parent ≤ children → peek() gives the minimum
• Max-Heap: parent ≥ children → peek() gives the maximum

Java's PriorityQueue<> is a min-heap by default.

Operation	Time
Insert	O(log n)
Peek (min/max)	O(1)
Remove min/max	O(log n)
Build heap from n elements	O(n)

---

When to Use

• Find the k-th largest/smallest element
• Always need quick access to current min or max
• Merge k sorted lists/arrays
• Scheduling problems (always process the next cheapest/fastest)
• Running median (two heaps)

---

Java Template

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

// Max-Heap
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

// Custom comparator: sort by second element descending
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[1] - a[1]);

// Common operations
pq.offer(element);   // insert — O(log n)
pq.poll();           // remove and return top — O(log n)
pq.peek();           // view top without removing — O(1)
pq.size();
pq.isEmpty();

---

Pattern: Top-K Elements

// K-th Largest Element in an Array
public int findKthLargest(int[] nums, int k) {
    // Maintain a min-heap of size k
    // The top of the heap is always the k-th largest seen so far
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();

    for (int num : nums) {
        minHeap.offer(num);
        if (minHeap.size() > k) {
            minHeap.poll(); // evict the smallest
        }
    }
    return minHeap.peek(); // the k-th largest
}

// Top K Frequent Elements
public int[] topKFrequent(int[] nums, int k) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int n : nums) map.put(n, map.getOrDefault(n, 0) + 1);

    // Min-heap ordered by element frequency
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);

    for (int key : map.keySet()) {
        pq.offer(new int[]{key, map.get(key)});
        if (pq.size() > k) pq.poll();
    }

    int[] res = new int[k];
    int i = k - 1;
    while (!pq.isEmpty()) res[i--] = pq.poll()[0];
    return res;
}

// Merge K Sorted Lists
public ListNode mergeKLists(ListNode[] lists) {
    if (lists == null || lists.length == 0) return null;

    PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);
    for (ListNode node : lists) {
        if (node != null) pq.offer(node);
    }

    ListNode dummy = new ListNode(0), curr = dummy;
    while (!pq.isEmpty()) {
        ListNode node = pq.poll();
        curr.next = node;
        curr = curr.next;
        if (node.next != null) pq.offer(node.next);
    }
    return dummy.next;
}

Why min-heap for "top K largest"? Keep only the K largest. The smallest of those K is the k-th largest overall.

---

Worked Example: Find Median from Data Stream

Maintain two heaps:

• maxHeap (lower half) — top is the largest small number
• minHeap (upper half) — top is the smallest large number

class MedianFinder {
    private PriorityQueue<Integer> lower; // max-heap
    private PriorityQueue<Integer> upper; // min-heap

    public MedianFinder() {
        lower = new PriorityQueue<>(Collections.reverseOrder());
        upper = new PriorityQueue<>();
    }

    public void addNum(int num) {
        lower.offer(num); // always add to lower first

        // Balance: lower's max must be ≤ upper's min
        if (!upper.isEmpty() && lower.peek() > upper.peek()) {
            upper.offer(lower.poll());
        }

        // Keep sizes balanced (lower can have at most 1 extra)
        if (lower.size() > upper.size() + 1) {
            upper.offer(lower.poll());
        } else if (upper.size() > lower.size()) {
            lower.offer(upper.poll());
        }
    }

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

---

Worked Example 2: Task Scheduler

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

    // Max-heap by frequency
    PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
    for (int f : freq) if (f > 0) maxHeap.offer(f);

    // Queue of [remaining_count, available_at_time]
    Queue<int[]> cooldown = new LinkedList<>();
    int time = 0;

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

        if (!maxHeap.isEmpty()) {
            int remaining = maxHeap.poll() - 1;
            if (remaining > 0) {
                cooldown.offer(new int[]{remaining, time + n});
            }
        }

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

---

LeetCode Problems

🟢 Easy

#	Problem	Pattern
703	Kth Largest Element in a Stream	Min-heap size k
1046	Last Stone Weight	Max-heap

🟡 Medium

#	Problem	Pattern
215	Kth Largest Element in an Array	Min-heap / quickselect
347	Top K Frequent Elements	Heap + frequency map
373	Find K Pairs with Smallest Sums	Min-heap
378	Kth Smallest in Sorted Matrix	Min-heap / binary search
621	Task Scheduler	Max-heap + cooldown
973	K Closest Points to Origin	Max-heap size k

🔴 Hard

#	Problem	Pattern
23	Merge K Sorted Lists	Min-heap
295	Find Median from Data Stream	Two heaps
480	Sliding Window Median	Two heaps + window
632	Smallest Range Covering Elements from K Lists	Min-heap + max tracking