Advanced Heaps & Priority Queues

1. Introduction: The Dynamic Sorter

If you need the maximum or minimum element of an array, you can scan it in $O(N)$ time. If you need it frequently, you can sort the array in $O(N \log N)$ time. But what if the array is constantly changing? What if new elements are arriving every second, and old elements are being removed? Resorting the array every time would be a catastrophic waste of CPU cycles.

This is where the Heap (implemented in Java as a PriorityQueue) shines. A Heap is a perfectly balanced binary tree that maintains a strict mathematical property: The parent node is always smaller (Min-Heap) or larger (Max-Heap) than its children. It can insert a new element or remove the extreme element in $O(\log N)$ time.

In advanced interviews, Heaps are used to solve stream processing problems, manage scheduling tasks, and perform K-way merges.

2. Core Concept: The Java PriorityQueue API

In Java, a PriorityQueue is a Min-Heap by default.

PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.offer(5); // O(log N) insertion
minHeap.poll();   // O(log N) removes and returns the smallest element
minHeap.peek();   // O(1) looks at the smallest element

To create a Max-Heap, you must pass a custom Comparator:

PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> Integer.compare(b, a));
// Or natively:
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

Note: Heaps are NOT fully sorted arrays. If you print a Heap, the elements will look jumbled. The ONLY guarantee is that the absolute Min/Max is at the root (index 0).

3. Advanced Code Example: Top K Frequent Elements

Problem Statement: (LeetCode 347) Given an integer array nums and an integer k, return the k most frequent elements.

The $O(N \log N)$ Trap: Count frequencies in a HashMap, put them in an Array, and sort the array. This is slow!

The $O(N \log K)$ Insight: We only care about the Top K! We can use a Min-Heap of size K. We insert elements into the Min-Heap. Because it's a Min-Heap, the least frequent element is always at the top. If the heap grows larger than K, we instantly poll() (kick out) the least frequent element. By the end of the loop, the heap will perfectly contain only the K most frequent elements!

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

public class TopKFrequent {
    public int[] topKFrequent(int[] nums, int k) {
        // 1. Count Frequencies
        Map<Integer, Integer> count = new HashMap<>();
        for (int num : nums) {
            count.put(num, count.getOrDefault(num, 0) + 1);
        }
        
        // 2. Initialize Min-Heap 
        // Compare based on the FREQUENCY (map.get(a)), not the actual number
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(
            (a, b) -> Integer.compare(count.get(a), count.get(b))
        );
        
        // 3. Maintain size K
        for (int num : count.keySet()) {
            minHeap.offer(num);
            if (minHeap.size() > k) {
                minHeap.poll(); // Evict the smallest frequency
            }
        }
        
        // 4. Extract Results
        int[] result = new int[k];
        for (int i = 0; i < k; i++) {
            result[i] = minHeap.poll();
        }
        
        return result;
    }
}

4. Advanced Code Example: Merge K Sorted Lists

Problem Statement: (LeetCode 23) You are given an array of k linked-lists, each linked-list is sorted in ascending order. Merge all the linked-lists into one sorted linked-list and return it.

The Insight: We want to find the absolute smallest node among the heads of the k lists. A Min-Heap is perfect for this. We put all k heads into the Min-Heap. We poll() the smallest node, attach it to our result, and if that node has a next node, we push the next node into the Min-Heap!

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

public class MergeKLists {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;
        
        // Min-Heap comparing ListNode values
        PriorityQueue<ListNode> minHeap = new PriorityQueue<>(
            (a, b) -> Integer.compare(a.val, b.val)
        );
        
        // Add the head of each list to the heap
        for (ListNode head : lists) {
            if (head != null) {
                minHeap.offer(head);
            }
        }
        
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        
        while (!minHeap.isEmpty()) {
            // Get the absolute smallest node available
            ListNode smallest = minHeap.poll();
            
            // Attach to our merged list
            tail.next = smallest;
            tail = tail.next;
            
            // If the list we just pulled from has more nodes, push the next one!
            if (smallest.next != null) {
                minHeap.offer(smallest.next);
            }
        }
        
        return dummy.next;
    }
}

Complexity Analysis:

• Time Complexity: $O(N \log K)$. Every single node ($N$ total nodes) is pushed and popped from a heap of max size $K$.
• Space Complexity: $O(K)$ for the Heap.

5. Advanced Code Example: Find Median from Data Stream (Two Heaps)

Problem Statement: (LeetCode 295) The median is the middle value in an ordered integer list. Implement the MedianFinder class which adds numbers from a data stream and can return the median at any time.

The Insight: If we keep a single sorted array, inserting into it takes $O(N)$ time, which is too slow for a real-time data stream. We can split the data in half! We maintain two Heaps:

1. A Max-Heap for the smaller half of the numbers.
2. A Min-Heap for the larger half of the numbers.

If we keep both heaps balanced in size, the Median is simply the root of the Max-Heap, or the average of both roots!

import java.util.PriorityQueue;

class MedianFinder {
    private PriorityQueue<Integer> smallHalf; // Max-Heap
    private PriorityQueue<Integer> largeHalf; // Min-Heap

    public MedianFinder() {
        // Java default is Min-Heap. Reverse it for Max-Heap.
        smallHalf = new PriorityQueue<>((a, b) -> Integer.compare(b, a));
        largeHalf = new PriorityQueue<>();
    }
    
    public void addNum(int num) {
        // Always add to the small half first
        smallHalf.offer(num);
        
        // 1. Ensure absolute ordering: every number in smallHalf MUST be <= largeHalf
        if (!smallHalf.isEmpty() && !largeHalf.isEmpty() && 
            smallHalf.peek() > largeHalf.peek()) {
            largeHalf.offer(smallHalf.poll());
        }
        
        // 2. Ensure size balance (smallHalf can be at most 1 element larger)
        if (smallHalf.size() > largeHalf.size() + 1) {
            largeHalf.offer(smallHalf.poll());
        } else if (largeHalf.size() > smallHalf.size()) {
            smallHalf.offer(largeHalf.poll());
        }
    }
    
    public double findMedian() {
        if (smallHalf.size() == largeHalf.size()) {
            return (smallHalf.peek() + largeHalf.peek()) / 2.0;
        } else {
            return smallHalf.peek(); // smallHalf is allowed to have 1 extra
        }
    }
}

Complexity Analysis:

• Time Complexity: $O(\log N)$ for addNum. $O(1)$ for findMedian.
• Space Complexity: $O(N)$ to store all numbers.

6. Common Mistakes Beginners Make

1. Using a Max-Heap for "Top K Largest"

   • The Mistake: Putting all elements into a Max-Heap and popping K times.
   • Why it's wrong: That takes $O(N \log N)$ to build and push all elements, plus $O(K \log N)$ to pop.
   • The Fix: ALWAYS use a Min-Heap of size K for "Top K Largest". If it exceeds size K, poll the smallest out. At the end, the heap contains the K largest elements in $O(N \log K)$ time. (Conversely, use a Max-Heap of size K for "Top K Smallest").

2. Removing random elements from a Heap

   • The Mistake: Calling heap.remove(targetObj).
   • Why it's wrong: Heaps do not have HashMaps built in. To find targetObj inside the tree, the Heap must do an $O(N)$ linear scan, destroying the $O(\log N)$ performance benefit.
   • The Fix: If you need to frequently remove random elements, you must use a TreeSet (which guarantees $O(\log N)$ for all operations) or a custom "HashHeap" (a heap combined with a HashMap).

7. Interview Q&A

Q1: How do you implement a Heap internally? Answer: It is surprisingly implemented using a standard 1D Array! The root is at index 0. For any node at index i, its left child is at 2i + 1 and its right child is at 2i + 2. Its parent is at (i - 1) / 2. This math perfectly maps a binary tree onto a contiguous array without needing Node pointers.

Q2: What is "Heapify" and how is it $O(N)$? Answer: If you push elements into a heap one by one, it takes $O(N \log N)$ time. However, if you already have a full array and pass it into a Heap constructor (or call PriorityQueue(Collection c)), an algorithm called "Heapify" is used. It starts from the bottom and sifts nodes downwards. The math proves that most nodes only travel 1 level, resulting in a strict $O(N)$ time complexity to build the entire heap!

Q3: Can a PriorityQueue store multiple elements with the exact same value? Answer: Yes! Unlike a TreeSet, a PriorityQueue perfectly handles duplicates. The heap math (<= and >=) accommodates duplicate values on the left or right subtrees without issue.

8. Practice Problems

1. Top K Frequent Elements (LeetCode 347)
   • Goal: Master the Size-K Min-Heap eviction pattern.
2. Merge K Sorted Lists (LeetCode 23)
   • Goal: Master K-way pointers in a Heap.
3. Find Median from Data Stream (LeetCode 295)
   • Goal: Master the Two-Heaps balancing logic.

9. Summary

• The Secret Rule: Use a Min-Heap to find the Top K Largest. Use a Max-Heap to find the Top K Smallest.
• Comparators: Know how to write (a, b) -> Integer.compare(a, b) natively.
• Data Streams: Heaps are the absolute best choice for real-time, dynamic data streams where you constantly need to query the extreme values.
• Two Heaps Pattern: Used for finding the Median by splitting data into a Max-Heap (smaller half) and a Min-Heap (larger half).