Collections

71. PriorityQueue

PriorityQueue is a heap-based priority queue: poll() always removes the smallest element (or the comparator-minimum); add/offer is O(log n); peek is O(1); iteration order is not sorted.

Java 21 (core language)

Explanation

PriorityQueue<E> is a min-heap by default (natural ordering — smallest first). Pass a Comparator to change priority. offer(e)/add(e) inserts in O(log n). poll() removes and returns the head (minimum) in O(log n). peek() returns the head without removing in O(1). remove(obj) for non-head elements is O(n) — PriorityQueue is not designed for arbitrary removal.

Important: iterating a PriorityQueue with for-each or iterator() does not yield elements in priority order — the heap is only partially ordered. To process in order, repeatedly call poll().

Common use: Dijkstra's shortest-path algorithm, top-K problems, scheduling by priority, merging sorted streams.

Example

import java.util.*;

public class PriorityQueueDemo {
    record Task(String name, int priority) {}

    public static void main(String[] args) {
        // Default: min-heap (natural ordering)
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        minHeap.addAll(List.of(5, 1, 8, 3, 2));
        System.out.print("Min-heap poll order: ");
        while (!minHeap.isEmpty()) System.out.print(minHeap.poll() + " ");
        System.out.println(); // 1 2 3 5 8

        // Max-heap via reversed comparator
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
        maxHeap.addAll(List.of(5, 1, 8, 3, 2));
        System.out.print("Max-heap poll order: ");
        while (!maxHeap.isEmpty()) System.out.print(maxHeap.poll() + " ");
        System.out.println(); // 8 5 3 2 1

        // Custom priority: lowest priority number = highest urgency
        PriorityQueue<Task> taskQ = new PriorityQueue<>(
            Comparator.comparingInt(Task::priority));
        taskQ.offer(new Task("Low priority",    10));
        taskQ.offer(new Task("Critical",         1));
        taskQ.offer(new Task("Medium priority",  5));
        taskQ.offer(new Task("Urgent",           2));

        System.out.println("\nTask processing order:");
        while (!taskQ.isEmpty()) {
            Task t = taskQ.poll();
            System.out.println("  [" + t.priority() + "] " + t.name());
        }

        // Top-K largest elements
        int K = 3;
        int[] numbers = {4, 1, 7, 2, 9, 3, 8, 5};
        PriorityQueue<Integer> topK = new PriorityQueue<>(K); // min-heap of size K
        for (int n : numbers) {
            topK.offer(n);
            if (topK.size() > K) topK.poll(); // remove smallest
        }
        System.out.println("\nTop " + K + " largest: " + new TreeSet<>(topK).descendingSet());
    }
}

Sources