Heaps & Priority Queues

🎯 Explain Like I'm 5...

Imagine you're a teacher with lots of students, and you always need to find the tallest or shortest student super quickly!

📏 Min Heap - Finding the Shortest Kid:

• All students line up in a special way
• The shortest student is ALWAYS in front!
• When the shortest student leaves, the next shortest automatically moves to the front! ⚡

🦒 Max Heap - Finding the Tallest Kid:

• All students line up in a special way
• The tallest student is ALWAYS in front!
• When the tallest student leaves, the next tallest automatically moves to the front! ⚡

🚀 Why Are Heaps Useful?

• You can ALWAYS find the smallest or largest element instantly (in O(1) time)!
• Adding or removing takes only O(log n) time - super fast even with millions of elements!
• Perfect for finding 'Top K' items, like top 10 high scores or k closest points!
• Used in scheduling tasks, finding median, and merging sorted lists!

🔧 Basic Heap Operations

Creating a Heap (PriorityQueue in Java)

HeapBasics.java

java

import java.util.PriorityQueue;
import java.util.Collections;
public class HeapBasics {
    public static void main(String[] args) {
        // Min Heap (default) - smallest element at top
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        // Max Heap - largest element at top (reverse order)
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        // Add elements to min heap
        minHeap.offer(5);  // offer() adds element
        minHeap.offer(2);
        minHeap.offer(8);
        minHeap.offer(1);
        minHeap.offer(10);
        System.out.println("Min Heap top (smallest): " + minHeap.peek());  // 1
        // Add elements to max heap
        maxHeap.offer(5);
        maxHeap.offer(2);
        maxHeap.offer(8);
        maxHeap.offer(1);
        maxHeap.offer(10);
        System.out.println("Max Heap top (largest): " + maxHeap.peek());   // 10
    }
}

Core Heap Operations

HeapOperations.java

java

import java.util.PriorityQueue;
public class HeapOperations {
    public static void main(String[] args) {
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        // 1. INSERT - Add elements (O(log n))
        heap.offer(15);  // offer() is preferred over add()
        heap.offer(10);
        heap.offer(20);
        heap.offer(8);
        heap.offer(25);
        System.out.println("Heap size: " + heap.size());  // 5
        // 2. PEEK - View top element without removing (O(1))
        System.out.println("Top element: " + heap.peek());  // 8 (smallest)
        System.out.println("Size after peek: " + heap.size());  // Still 5
        // 3. POLL - Remove and return top element (O(log n))
        int smallest = heap.poll();
        System.out.println("Removed: " + smallest);  // 8
        System.out.println("New top: " + heap.peek());  // 10
        System.out.println("Size after poll: " + heap.size());  // 4
        // 4. Check if empty
        System.out.println("Is empty? " + heap.isEmpty());  // false
        // 5. Remove all elements in sorted order
        System.out.println("\nRemoving all elements:");
        while (!heap.isEmpty()) {
            System.out.print(heap.poll() + " ");  // 10 15 20 25
        }
        System.out.println("\nIs empty now? " + heap.isEmpty());  // true
    }
}

Understanding Heap Structure

HeapStructure.java

java

import java.util.PriorityQueue;
public class HeapStructure {
    public static void main(String[] args) {
        /*
         * HEAP STRUCTURE - Complete Binary Tree stored in Array
         *
         * For Min Heap with [1, 3, 5, 7, 9, 11, 13]:
         *
         *           1           <- root (index 0)
         *         /   \
         *        3     5        <- level 1
         *       / \   / \
         *      7   9 11 13      <- level 2
         *
         * Array representation: [1, 3, 5, 7, 9, 11, 13]
         *                        0  1  2  3  4   5   6  <- indices
         *
         * For any element at index i:
         * - Parent index: (i - 1) / 2
         * - Left child index: 2 * i + 1
         * - Right child index: 2 * i + 2
         *
         * HEAP PROPERTY:
         * Min Heap: Parent <= Children (smallest at top)
         * Max Heap: Parent >= Children (largest at top)
         */
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        // Build the heap from example above
        int[] values = {1, 3, 5, 7, 9, 11, 13};
        for (int val : values) {
            minHeap.offer(val);
        }
        System.out.println("Heap property demonstration:");
        System.out.println("Root (minimum): " + minHeap.peek());  // 1
        // Remove elements to see heap rebalancing
        System.out.println("\nRemoving elements in order:");
        while (!minHeap.isEmpty()) {
            System.out.print(minHeap.poll() + " ");
            // Heap automatically rebalances after each removal!
        }
        // Output: 1 3 5 7 9 11 13 (sorted order)
    }
}

💡 Common Problems & Solutions

Problem 1: Kth Largest Element

Find the kth largest element in an array - like finding the 3rd tallest student!

💡 How it works (Min Heap of Size K):

The Challenge: Find the kth largest element efficiently (better than sorting O(n log n))

The Solution (Use Min Heap of Size K):

1. Create a min heap to store K largest elements

2. For each number in array:

• Add number to heap

• If heap size > k, remove the smallest (poll)

3. After processing all numbers:

→ The top of heap (smallest of K largest) is the kth largest!

Key Insight: By keeping only K elements, the smallest one is exactly the kth largest overall

Visual Example:

Array: [3, 2, 1, 5, 6, 4], k = 3 (find 3rd largest)

Process each number:
Add 3: heap = [3]
Add 2: heap = [2, 3]
Add 1: heap = [1, 2, 3]
Add 5: heap = [1, 2, 3, 5] → size > 3, poll 1 → heap = [2, 3, 5]
Add 6: heap = [2, 3, 5, 6] → size > 3, poll 2 → heap = [3, 5, 6]
Add 4: heap = [3, 4, 5, 6] → size > 3, poll 3 → heap = [4, 5, 6]

Final heap (3 largest): [4, 5, 6]
Min heap top: 4 ← This is the 3rd largest! ✓

Why it works:
Heap keeps: 6 (largest), 5 (2nd), 4 (3rd)
Smallest of these 3 = 3rd largest overall

⏱️ Time Complexity: O(n log k) - better than O(n log n) sorting

💾 Space Complexity: O(k) - only store k elements

KthLargest.java

java

import java.util.PriorityQueue;
public class KthLargest {
    /*
     * STRATEGY: Use Min Heap of size K
     * - Keep only K largest elements in heap
     * - The root (minimum of these K elements) is the Kth largest!
     *
     * Example: Find 3rd largest in [3, 2, 1, 5, 6, 4], k=3
     * - Min heap keeps: [4, 5, 6]
     * - Top of heap (4) is the 3rd largest!
     *
     * Time: O(n log k), Space: O(k)
     */
    public static int findKthLargest(int[] nums, int k) {
        // Min heap to keep K largest elements
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int num : nums) {
            minHeap.offer(num);
            // Keep heap size at K
            if (minHeap.size() > k) {
                minHeap.poll();  // Remove smallest
            }
        }
        // Top of heap is Kth largest
        return minHeap.peek();
    }
    public static void main(String[] args) {
        int[] nums = {3, 2, 1, 5, 6, 4};
        int k = 3;
        int result = findKthLargest(nums, k);
        System.out.println(k + "rd largest element: " + result);  // 4
        // More examples
        int[] nums2 = {3, 2, 3, 1, 2, 4, 5, 5, 6};
        System.out.println("4th largest: " + findKthLargest(nums2, 4));  // 4
        System.out.println("1st largest: " + findKthLargest(nums2, 1));  // 6
    }
}

Problem 2: Top K Frequent Elements

Find the k most frequent elements in an array using a heap!

💡 How it works (Frequency Map + Min Heap):

The Challenge: Find k most frequent elements efficiently

The Solution (Two Steps):

1. Count frequencies using HashMap

2. Use min heap (size k) ordered by frequency:

• Add each unique number to heap

• If heap size > k, remove least frequent

3. Heap contains k most frequent elements!

The Trick: Min heap keeps elements with HIGHEST frequencies by removing lowest

Visual Example:

Array: [1,1,1,2,2,3], k = 2 (find 2 most frequent)

Step 1: Count frequencies
freq = {1: 3, 2: 2, 3: 1}

Step 2: Build min heap (ordered by frequency)
Process 1 (freq=3): heap = [1]
Process 2 (freq=2): heap = [2, 1] (min heap by freq)
Process 3 (freq=1): heap = [3, 2, 1]
Size > k, remove min freq (3) → heap = [2, 1]

Final heap: [2, 1]
• 1 appears 3 times
• 2 appears 2 times
These are the 2 most frequent! ✓

Key: Min heap removes LEAST frequent, keeping most frequent

⏱️ Time Complexity: O(n log k) - n for counting, log k for heap operations

💾 Space Complexity: O(n) - storing frequencies

TopKFrequent.java

java

import java.util.*;
public class TopKFrequent {
    /*
     * STRATEGY: Use HashMap + Min Heap
     * 1. Count frequencies with HashMap
     * 2. Keep K most frequent elements in min heap (ordered by frequency)
     * 3. If heap size > K, remove element with lowest frequency
     *
     * Time: O(n log k), Space: O(n)
     */
    public static int[] topKFrequent(int[] nums, int k) {
        // Step 1: Count frequencies
        Map<Integer, Integer> freqMap = new HashMap<>();
        for (int num : nums) {
            freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
        }
        // Step 2: Min heap ordered by frequency
        // Custom comparator: compare by frequency (value in map)
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(
            (a, b) -> freqMap.get(a) - freqMap.get(b)
        );
        // Step 3: Keep only K most frequent elements
        for (int num : freqMap.keySet()) {
            minHeap.offer(num);
            if (minHeap.size() > k) {
                minHeap.poll();  // Remove least frequent
            }
        }
        // Step 4: Build result array
        int[] result = new int[k];
        for (int i = 0; i < k; i++) {
            result[i] = minHeap.poll();
        }
        return result;
    }
    public static void main(String[] args) {
        int[] nums1 = {1, 1, 1, 2, 2, 3};
        int k1 = 2;
        int[] result1 = topKFrequent(nums1, k1);
        System.out.println("Top " + k1 + " frequent: " + Arrays.toString(result1));
        // Output: [2, 1] or [1, 2] (both appear most frequently)
        int[] nums2 = {4, 4, 4, 6, 6, 2};
        int k2 = 2;
        int[] result2 = topKFrequent(nums2, k2);
        System.out.println("Top " + k2 + " frequent: " + Arrays.toString(result2));
        // Output: [6, 4] (4 appears 3 times, 6 appears 2 times)
    }
}

Problem 3: Merge K Sorted Lists

Efficiently merge multiple sorted lists using a min heap!

💡 How it works (Min Heap for Merging):

The Challenge: Merge k sorted linked lists into one sorted list

The Solution (Use Min Heap):

1. Add first node from each list to min heap

2. While heap is not empty:

• Poll smallest node from heap

• Add it to result list

• Add next node from that list to heap

3. Result is merged sorted list!

Why This is Smart: Heap always gives us the next smallest element across all k lists in O(log k)

Visual Example:

Lists: [[1,4,5], [1,3,4], [2,6]]

Step 1: Add first node from each list
Heap = [1(L1), 1(L2), 2(L3)]

Step 2: Poll smallest = 1(L1), add to result
Result = [1]
Add next from L1 (4) → Heap = [1(L2), 2(L3), 4(L1)]

Step 3: Poll smallest = 1(L2), add to result
Result = [1, 1]
Add next from L2 (3) → Heap = [2(L3), 3(L2), 4(L1)]

Step 4: Poll smallest = 2(L3), add to result
Result = [1, 1, 2]
Add next from L3 (6) → Heap = [3(L2), 4(L1), 6(L3)]

Continue until heap empty...
Final result: [1, 1, 2, 3, 4, 4, 5, 6] ✓

⏱️ Time Complexity: O(N log k) - N total nodes, log k heap operations

💾 Space Complexity: O(k) - heap stores at most k nodes

MergeKLists.java

java

import java.util.PriorityQueue;
// Definition for singly-linked list node
class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}
public class MergeKLists {
    /*
     * STRATEGY: Use Min Heap to track smallest elements
     * 1. Add first node from each list to min heap
     * 2. Poll smallest node, add to result
     * 3. Add next node from that list to heap
     * 4. Repeat until heap is empty
     *
     * Example: [[1,4,5], [1,3,4], [2,6]]
     * Heap operations:
     * - Initial: [1(L1), 1(L2), 2(L3)]
     * - Poll 1(L1), add 4: [1(L2), 2(L3), 4(L1)]
     * - Poll 1(L2), add 3: [2(L3), 3(L2), 4(L1)]
     * - Continue until all merged!
     *
     * Time: O(N log k) where N = total nodes, k = number of lists
     * Space: O(k) for heap
     */
    public static ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        // Min heap ordered by node value
        PriorityQueue<ListNode> minHeap = new PriorityQueue<>(
            (a, b) -> a.val - b.val
        );
        // Add first node from each list
        for (ListNode node : lists) {
            if (node != null) {
                minHeap.offer(node);
            }
        }
        // Dummy node to build result list
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;
        // Merge process
        while (!minHeap.isEmpty()) {
            // Get smallest node
            ListNode smallest = minHeap.poll();
            current.next = smallest;
            current = current.next;
            // Add next node from same list
            if (smallest.next != null) {
                minHeap.offer(smallest.next);
            }
        }
        return dummy.next;
    }
    public static void main(String[] args) {
        // Create test lists: [[1,4,5], [1,3,4], [2,6]]
        ListNode list1 = new ListNode(1);
        list1.next = new ListNode(4);
        list1.next.next = new ListNode(5);
        ListNode list2 = new ListNode(1);
        list2.next = new ListNode(3);
        list2.next.next = new ListNode(4);
        ListNode list3 = new ListNode(2);
        list3.next = new ListNode(6);
        ListNode[] lists = {list1, list2, list3};
        ListNode result = mergeKLists(lists);
        // Print merged list
        System.out.print("Merged list: ");
        while (result != null) {
            System.out.print(result.val + " ");
            result = result.next;
        }
        // Output: 1 1 2 3 4 4 5 6
    }
}

Problem 4: Find Median from Data Stream

Use two heaps to find the median of a stream of numbers efficiently!

💡 How it works (Two Heaps Technique):

The Challenge: Find median from a continuous stream of numbers efficiently

The Solution (Two Heaps):

1. Use two heaps to split numbers in half:

• Max heap (left): stores smaller half

• Min heap (right): stores larger half

2. Add number strategy:

• Add to max heap first

• Move max heap's top to min heap (balance)

• If min heap larger, move back to max heap

3. Find median:

• Odd count: top of max heap (larger heap)

• Even count: average of both tops

Visualization:

Max heap stores smaller half | Min heap stores larger half

Visual Example:

Stream: [1, 2, 3, 4, 5]

Add 1:
MaxHeap: [1] | MinHeap: []
Median: 1.0 (odd, top of max)

Add 2:
MaxHeap: [1] | MinHeap: [2]
Median: 1.5 (even, avg of 1 and 2)

Add 3:
MaxHeap: [2, 1] | MinHeap: [3]
Median: 2.0 (odd, top of max)

Add 4:
MaxHeap: [2, 1] | MinHeap: [3, 4]
Median: 2.5 (even, avg of 2 and 3)

Add 5:
MaxHeap: [3, 2, 1] | MinHeap: [4, 5]
Median: 3.0 (odd, top of max) ✓

Key: Max heap stores smaller half, always ≥ min heap size

⏱️ Time Complexity: O(log n) per add, O(1) to find median

💾 Space Complexity: O(n) - storing all numbers

MedianFinder.java

java

import java.util.PriorityQueue;
import java.util.Collections;
public class MedianFinder {
    /*
     * STRATEGY: Two Heaps Approach
     *
     * Use two heaps to maintain median:
     * - Max Heap (left): stores smaller half of numbers
     * - Min Heap (right): stores larger half of numbers
     *
     * Visualization:
     *    Max Heap (left)    |    Min Heap (right)
     *    [smaller half]     |    [larger half]
     *         5 4 3         |         6 7 8
     *           ^           |         ^
     *        largest        |      smallest
     *
     * Median is either:
     * - Middle element if odd count (top of larger heap)
     * - Average of two middle elements if even count
     *
     * Time: addNum O(log n), findMedian O(1)
     * Space: O(n)
     */
    private PriorityQueue<Integer> maxHeap;  // Left half (smaller numbers)
    private PriorityQueue<Integer> minHeap;  // Right half (larger numbers)
    public MedianFinder() {
        maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        minHeap = new PriorityQueue<>();
    }
    public void addNum(int num) {
        // Add to maxHeap first
        maxHeap.offer(num);
        // Balance: move largest from maxHeap to minHeap
        minHeap.offer(maxHeap.poll());
        // Keep maxHeap size >= minHeap size
        if (maxHeap.size() < minHeap.size()) {
            maxHeap.offer(minHeap.poll());
        }
    }
    public double findMedian() {
        if (maxHeap.size() > minHeap.size()) {
            // Odd count: return middle element
            return maxHeap.peek();
        } else {
            // Even count: return average of two middle elements
            return (maxHeap.peek() + minHeap.peek()) / 2.0;
        }
    }
    public static void main(String[] args) {
        MedianFinder mf = new MedianFinder();
        mf.addNum(1);
        System.out.println("Added 1, median: " + mf.findMedian());  // 1.0
        mf.addNum(2);
        System.out.println("Added 2, median: " + mf.findMedian());  // 1.5
        mf.addNum(3);
        System.out.println("Added 3, median: " + mf.findMedian());  // 2.0
        mf.addNum(4);
        System.out.println("Added 4, median: " + mf.findMedian());  // 2.5
        mf.addNum(5);
        System.out.println("Added 5, median: " + mf.findMedian());  // 3.0
        // Stream: [1, 2, 3, 4, 5]
        // MaxHeap (left): [3, 2, 1] - stores smaller half
        // MinHeap (right): [4, 5] - stores larger half
        // Median: 3 (middle element)
    }
}

🔑 Key Points to Remember

1️⃣Heaps are complete binary trees stored in arrays
2️⃣Min heap: parent is smaller than children; Max heap: parent is larger
3️⃣Insert and remove operations are O(log n) - very efficient!
4️⃣Peek (view top) is O(1) - instant access to min/max element
5️⃣Java's PriorityQueue is a min heap by default
6️⃣Perfect for finding kth largest/smallest, top k elements, and median

💪 Practice Problems

• Last Stone Weight
• K Closest Points to Origin
• Task Scheduler
• Find K Pairs with Smallest Sums
• Meeting Rooms II
• Reorganize String