Java PriorityQueue — Heap-Based Ordering

PriorityQueue is a queue where elements are dequeued in priority order rather than insertion order. By default it’s a min-heap — the smallest element comes out first.

---

How It Works

offer(30), offer(10), offer(20), offer(5)

Internal min-heap (binary tree stored as array):
         5
        / \
      10   20
     /
    30

Array: [5, 10, 20, 30]

poll() → 5
         10
        / \
      30   20

poll() → 10
         20
        /
      30

• offer() — inserts and bubbles up (heapify-up). O(log n).
• poll() — removes root, moves last element to root, bubbles down. O(log n).
• peek() — returns root without removing. O(1).

---

Basic Usage

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(30);
pq.offer(10);
pq.offer(20);
pq.offer(5);

pq.peek();  // 5 (smallest)
pq.poll();  // 5
pq.poll();  // 10
pq.poll();  // 20
pq.poll();  // 30

Important: Iterating a PriorityQueue does NOT give elements in sorted order. Only poll() guarantees priority order.

PriorityQueue<Integer> pq = new PriorityQueue<>(List.of(30, 10, 20, 5));
System.out.println(pq);  // [5, 10, 20, 30] ← might look sorted, but not guaranteed

for (int n : pq) {
    System.out.print(n + " ");  // ORDER NOT GUARANTEED!
}

---

Big-O Complexity

Operation	Time
offer(e)	O(log n)
poll()	O(log n)
peek()	O(1)
contains(e)	O(n)
remove(e)	O(n)
size()	O(1)

---

Max-Heap

Reverse the natural order to get a max-heap:

PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
maxHeap.offer(10);
maxHeap.offer(30);
maxHeap.offer(20);

maxHeap.poll();  // 30 (largest)
maxHeap.poll();  // 20
maxHeap.poll();  // 10

Or with Comparator.reverseOrder():

PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());

---

Custom Comparator

Order by any criteria:

// Priority by string length (shortest first)
PriorityQueue<String> pq = new PriorityQueue<>(Comparator.comparingInt(String::length));
pq.offer("banana");
pq.offer("fig");
pq.offer("apple");

pq.poll();  // "fig" (length 3)
pq.poll();  // "apple" (length 5)
pq.poll();  // "banana" (length 6)

Task Scheduling by Priority

record Task(String name, int priority) {}

PriorityQueue<Task> taskQueue = new PriorityQueue<>(
    Comparator.comparingInt(Task::priority)
);

taskQueue.offer(new Task("Send email", 3));
taskQueue.offer(new Task("Fix critical bug", 1));
taskQueue.offer(new Task("Update docs", 5));

taskQueue.poll();  // Task[name=Fix critical bug, priority=1]
taskQueue.poll();  // Task[name=Send email, priority=3]

---

Classic Problem: Top-K Elements

Find the K largest elements from a stream:

public List<Integer> topK(int[] nums, int k) {
    // Min-heap of size k — the smallest of the top-k stays at root
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();

    for (int num : nums) {
        minHeap.offer(num);
        if (minHeap.size() > k) {
            minHeap.poll();  // remove smallest → keep only top-k
        }
    }

    return new ArrayList<>(minHeap);  // the k largest elements
}

topK(new int[]{3, 1, 4, 1, 5, 9, 2, 6}, 3);
// Returns: [5, 6, 9] (top 3 largest)

Why min-heap for top-K? We keep the k largest. When a new element is bigger than the heap’s min, it replaces it. The heap’s root is always the kth-largest.

---

Practical Example: Merge K Sorted Lists

public List<Integer> mergeKSorted(List<List<Integer>> lists) {
    PriorityQueue<int[]> pq = new PriorityQueue<>(
        Comparator.comparingInt(a -> a[0])  // sort by value
    );

    // Seed with first element of each list: [value, listIndex, elementIndex]
    for (int i = 0; i < lists.size(); i++) {
        if (!lists.get(i).isEmpty()) {
            pq.offer(new int[]{lists.get(i).get(0), i, 0});
        }
    }

    List<Integer> result = new ArrayList<>();
    while (!pq.isEmpty()) {
        int[] entry = pq.poll();
        result.add(entry[0]);

        int nextIdx = entry[2] + 1;
        if (nextIdx < lists.get(entry[1]).size()) {
            pq.offer(new int[]{lists.get(entry[1]).get(nextIdx), entry[1], nextIdx});
        }
    }
    return result;
}

---

Important Restrictions

1. No null elements — throws NullPointerException.
2. Not thread-safe — use PriorityBlockingQueue for concurrency.
3. Iterator order ≠ priority order — only poll() is ordered.
4. Elements must be Comparable or you must provide a Comparator.

---

Key Takeaways

1. PriorityQueue is a min-heap — poll() returns the smallest element.
2. Use Collections.reverseOrder() for a max-heap.
3. Only poll() order is guaranteed — iteration is NOT sorted.
4. O(log n) for offer/poll, O(1) for peek.
5. Classic use cases: top-K, task scheduling, Dijkstra’s algorithm, merge-K-sorted.
6. Provide a Comparator for custom objects.

---

What’s Next?

Next: Iterators and for-each — traversing collections, fail-fast behaviour, and Spliterator.