Heaps and Priority Queues: Principles and High-Frequency Problems

Core Concept of Heaps

A Heap (specifically a Binary Heap) is a complete binary tree satisfying the heap property:

• Max Heap: Parent node value $\ge$ child node values.
• Min Heap: Parent node value $\le$ child node values.

In Java, PriorityQueue implements a Min Heap by default.

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

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

// Core Operations
pq.offer(x);       // Insert element, O(log N)
pq.poll();         // Extract root, O(log N)
pq.peek();         // View root, O(1)
pq.size();
pq.isEmpty();

Top K Problems

K-th Largest Element in an Array (LeetCode 215)

Approach: Maintain a Min Heap of size $K$. When the heap exceeds size $K$, the smallest elements are discarded, leaving the largest $K$ elements in the heap. The top of the heap will be the $K$-th largest.

int findKthLargest(int[] nums, int k) {
    PriorityQueue<Integer> minHeap = new PriorityQueue<>(k);
    for (int num : nums) {
        minHeap.offer(num);
        if (minHeap.size() > k) {
            minHeap.poll(); // Remove the smallest current element
        }
    }
    return minHeap.peek(); // The k-th largest is at the root
}

Note: For O(N) average time complexity, see the Quick Select algorithm in the Sorting section.

Top K Frequent Elements (LeetCode 347)

int[] topKFrequent(int[] nums, int k) {
    // 1. Map frequencies
    Map<Integer, Integer> counts = new HashMap<>();
    for (int n : nums) counts.merge(n, 1, Integer::sum);
    
    // 2. Min Heap based on frequency
    PriorityQueue<int[]> minHeap = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
    for (var entry : counts.entrySet()) {
        minHeap.offer(new int[]{entry.getKey(), entry.getValue()});
        if (minHeap.size() > k) {
            minHeap.poll();
        }
    }
    
    // 3. Extract results
    return minHeap.stream().mapToInt(a -> a[0]).toArray();
}

K Closest Points to Origin (LeetCode 973)

int[][] kClosest(int[][] points, int k) {
    // Max Heap to discard furthest points and keep k closest
    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[] p : points) {
        maxHeap.offer(p);
        if (maxHeap.size() > k) maxHeap.poll();
    }
    return maxHeap.toArray(new int[0][]);
}

Find Median from Data Stream (LeetCode 295)

Strategy: Split the data into two halves. Use a Max Heap for the smaller half and a Min Heap for the larger half. Maintain a size difference $\le 1$.

class MedianFinder {
    // Stores the smaller half (Max Heap)
    PriorityQueue<Integer> small = new PriorityQueue<>(Collections.reverseOrder());
    // Stores the larger half (Min Heap)
    PriorityQueue<Integer> large = new PriorityQueue<>();

    void addNum(int num) {
        small.offer(num);
        large.offer(small.poll()); // Balance by moving largest of "small" to "large"
        
        // Ensure small.size() >= large.size()
        if (small.size() < large.size()) {
            small.offer(large.poll());
        }
    }

    double findMedian() {
        if (small.size() > large.size()) return small.peek();
        return (small.peek() + large.peek()) / 2.0;
    }
}

Merge K Sorted Lists (LeetCode 23)

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);
    ListNode tail = dummy;
    
    while (!pq.isEmpty()) {
        ListNode smallest = pq.poll();
        tail.next = smallest;
        tail = tail.next;
        // If the processed list has more nodes, add the next one to the heap
        if (smallest.next != null) pq.offer(smallest.next);
    }
    return dummy.next;
}

Complexity: O(N log K), where $N$ is total nodes and $K$ is the number of linked lists.

Sliding Window Maximum (LeetCode 239)

While Monotonic Queue is the optimal O(N) solution (see Stack section), a Heap with Lazy Removal is a common alternative:

int[] maxSlidingWindow(int[] nums, int k) {
    int n = nums.length;
    int[] results = new int[n - k + 1];
    // Max Heap storing [value, index]
    PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a, b) -> b[0] - a[0]);
    
    for (int i = 0; i < n; i++) {
        maxHeap.offer(new int[]{nums[i], i});
        if (i >= k - 1) {
            // Lazy Removal: pop until the heap root is within the current window
            while (maxHeap.peek()[1] <= i - k) {
                maxHeap.poll();
            }
            results[i - k + 1] = maxHeap.peek()[0];
        }
    }
    return results;
}

Manual Min-Heap Implementation (Architecture Essential)

Understanding how a heap is stored in an array (Parent $i \rightarrow$ Children $2i+1, 2i+2$):

class MinHeap {
    private int[] data;
    private int size;
    
    public MinHeap(int capacity) { data = new int[capacity]; }
    
    public void offer(int val) {
        data[size] = val;
        siftUp(size++);
    }
    
    public int poll() {
        int root = data[0];
        data[0] = data[--size];
        siftDown(0);
        return root;
    }
    
    private void siftUp(int i) {
        while (i > 0) {
            int parent = (i - 1) / 2;
            if (data[parent] <= data[i]) break;
            swap(i, parent);
            i = parent;
        }
    }
    
    private void siftDown(int i) {
        while (2 * i + 1 < size) {
            int smallerChild = 2 * i + 1; // Start with left
            int rightChild = 2 * i + 2;
            if (rightChild < size && data[rightChild] < data[smallerChild]) {
                smallerChild = rightChild;
            }
            if (data[i] <= data[smallerChild]) break;
            swap(i, smallerChild);
            i = smallerChild;
        }
    }
    
    private void swap(int a, int b) {
        int temp = data[a]; data[a] = data[b]; data[b] = temp;
    }
}

Summary