Priority Queues (Heaps) Basics

1. Introduction: The VIP Line

Imagine you are at an emergency room. A Queue data structure operates on First-In, First-Out (FIFO); whoever arrives first gets treated first. But if someone arrives with a stubbed toe, and five minutes later someone arrives with a heart attack, the FIFO queue fails. We need a system where the "Highest Priority" patient jumps to the front of the line instantly.

This is a Priority Queue. Under the hood, it is almost always implemented using a data structure called a Heap. A Heap dynamically maintains the minimum (or maximum) element at the absolute front of the line, allowing $O(1)$ access to the VIP, and $O(\log N)$ time to insert new VIPs or remove them.

2. Core Concept: The Binary Heap Structure

A Heap is a Complete Binary Tree. This means every level of the tree is fully populated except possibly the last level, which is filled strictly from left to right.

Because of this strict geometric structure, we don't need Node objects with left and right pointers! We can store the entire tree inside a standard flat array:

• The root is at index 0.
• The left child of index i is at 2 * i + 1.
• The right child of index i is at 2 * i + 2.
• The parent of index i is at (i - 1) / 2.

The Heap Property:

• Min-Heap: Every parent node is $\le$ its children. The absolute minimum is at the root.
• Max-Heap: Every parent node is $\ge$ its children. The absolute maximum is at the root.

(Note: The left child and right child have no sorted relationship with each other! A Heap is NOT a Binary Search Tree).

3. Beginner Code Example: Using Java's PriorityQueue

In Java, you do not need to build a Heap from scratch. You use the java.util.PriorityQueue class. By default, it is a Min-Heap.

import java.util.PriorityQueue;

public class BasicMinHeap {
    public static void demonstrateHeap() {
        // Create a Min-Heap
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        
        // 1. Insertion (O(log N))
        // Internally, it adds to the end of the array and "bubbles up"
        minHeap.offer(10); 
        minHeap.offer(5);
        minHeap.offer(20);
        minHeap.offer(1);
        
        // 2. Peek (O(1))
        // Look at the smallest element without removing it
        System.out.println("Smallest: " + minHeap.peek()); // Output: 1
        
        // 3. Removal (O(log N))
        // Removes the root, moves the last element to the root, and "bubbles down"
        while (!minHeap.isEmpty()) {
            System.out.print(minHeap.poll() + " "); // Output: 1 5 10 20
        }
    }
}

4. Intermediate Code Example: Max-Heap and Custom Objects

To create a Max-Heap, you must pass a custom Comparator into the constructor.

Problem Statement: (LeetCode 1046) Last Stone Weight. You have a collection of stones. Each turn, you smash the two heaviest stones together. If they have equal weight, both are destroyed. If unequal, the smaller one is destroyed and the larger one shrinks by the smaller's weight. Return the weight of the last remaining stone.

The Insight: We constantly need the TWO largest elements in a dynamic array. A Max-Heap is the perfect tool.

import java.util.Collections;
import java.util.PriorityQueue;

public class LastStoneWeight {
    public static int lastStoneWeight(int[] stones) {
        // Create a Max-Heap using Collections.reverseOrder()
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        
        // Alternatively using Lambda (slower but more flexible):
        // PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> Integer.compare(b, a));
        
        // Populate the heap
        for (int stone : stones) {
            maxHeap.offer(stone);
        }
        
        // Smash stones while at least 2 remain
        while (maxHeap.size() > 1) {
            int heavy1 = maxHeap.poll(); // The heaviest
            int heavy2 = maxHeap.poll(); // The second heaviest
            
            if (heavy1 != heavy2) {
                // Put the remaining crushed stone back into the heap
                maxHeap.offer(heavy1 - heavy2);
            }
        }
        
        // Return the last stone, or 0 if all were destroyed
        return maxHeap.isEmpty() ? 0 : maxHeap.poll();
    }
}

5. Advanced Code Example: Complex Custom Comparators

Heaps become incredibly powerful when you store complex Objects instead of simple Integers.

Problem Statement: (LeetCode 973) K Closest Points to Origin. Given an array of points where points[i] = [x, y] represents a point on a 2D plane and an integer k, return the k closest points to the origin (0, 0).

The Insight: We want the "Top K Smallest" distances.

• The naive way: Min-Heap of size $N$, pop $K$ times. ($O(N \log N)$ time).
• The Pro way: Max-Heap of size $K$. As we iterate, if a new point is closer than the absolute furthest point currently in our Max-Heap (the root), we kick the root out and add the new point! Time drops to $O(N \log K)$.

import java.util.PriorityQueue;

public class KClosestPoints {
    public int[][] kClosest(int[][] points, int k) {
        // Max-Heap: We want the LARGEST distance at the top so we can evict it!
        // We compare based on distance squared: (x^2 + y^2)
        PriorityQueue<int[]> maxHeap = new PriorityQueue<>(
            (p1, p2) -> Integer.compare((p2[0]*p2[0] + p2[1]*p2[1]), 
                                        (p1[0]*p1[0] + p1[1]*p1[1]))
        );
        
        for (int[] point : points) {
            maxHeap.offer(point);
            
            // If we exceed capacity K, evict the FURTHEST point!
            if (maxHeap.size() > k) {
                maxHeap.poll();
            }
        }
        
        // Extract the K remaining (closest) points
        int[][] result = new int[k][2];
        for (int i = 0; i < k; i++) {
            result[i] = maxHeap.poll();
        }
        
        return result;
    }
}

6. Common Mistakes Beginners Make

1. Reversing the Comparator logic

   • The Mistake: (a, b) -> a - b for Max-Heap.
   • Why it's wrong: a - b is ascending order (Min-Heap). b - a is descending order (Max-Heap). Always use Integer.compare(b, a) to avoid catastrophic integer overflow bugs.

2. Using .remove(Object)

   • The Mistake: heap.remove(5)
   • Why it's wrong: poll() removes the root in $O(\log N)$. .remove(Object) searches the entire array to find the object, taking $O(N)$ time. If you do this frequently, you are breaking the performance of the heap.

3. Iterating over the Heap directly

   • The Mistake: for (int num : heap) { System.out.println(num); }
   • Why it's wrong: The internal array is a Tree, not a sorted list. Iterating directly will print the numbers in a bizarre, semi-sorted order. You MUST use a while (!heap.isEmpty()) { heap.poll(); } loop if you want to extract elements in strictly sorted order.

7. Interview Q&A

Q1: How does a PriorityQueue resize itself? Answer: Just like an ArrayList, the internal array has a capacity. When it fills up, Java creates a new array that is roughly 50% to 100% larger, copies all elements over, and continues. This is an amortized $O(1)$ operation, but causes an occasional $O(N)$ spike.

Q2: What is the Time Complexity to build a Heap from an existing array? Answer: If you push elements one by one, it takes $O(N \log N)$. But if you pass an entire Collection into the PriorityQueue constructor, it uses an internal algorithm called "Heapify" which builds the heap in strictly $O(N)$ time.

Q3: When should I use a TreeSet instead of a PriorityQueue? Answer: A PriorityQueue only gives you fast access to ONE element (the min or max). If you need fast access to both the Min AND the Max simultaneously, or if you need to rapidly search for arbitrary elements, or if you need elements strictly unique, use a TreeSet.

8. Practice Problems

1. Last Stone Weight (LeetCode 1046)
   • Goal: Basic Max-Heap mechanics.
2. Kth Largest Element in an Array (LeetCode 215)
   • Goal: Master the Size-K Min-Heap pattern.
3. K Closest Points to Origin (LeetCode 973)
   • Hint: Master writing complex Object comparators.

9. Summary

• Priority Queue: A Queue that always places the highest priority (min or max) element at the front.
• Java Default: PriorityQueue<> is a Min-Heap. Use Collections.reverseOrder() for a Max-Heap.
• Operations: offer() inserts in $O(\log N)$. poll() removes in $O(\log N)$. peek() views in $O(1)$.
• The Top K Rule: For "Top K Largest", use a Min-Heap of size K. For "Top K Smallest", use a Max-Heap of size K.