Priority queues intro

A priority queue removes the value with the **highest priority** next, whatever its arrival time. What “highest” means is not a property of the structure but of an ordering: in Java a Comparator (or the natural order of Comparable values) decides which of two elements comes out first. The element that sorts first leaves first.

Because the comparator is the definition of priority, it must be a consistent total order: if a comes before b and b before c, then a comes before c, and the answer never changes while the element is in the queue.

1static void order() {
2    PriorityQueue<String> byLength = new PriorityQueue<>(Comparator.comparingInt(String::length));
3    byLength.offer("pear"); byLength.offer("fig"); byLength.offer("banana");
4    System.out.println(byLength.poll());       // fig: the shortest word has the highest priority
5}

PriorityQueue stores a binary heap in a plain array. offer appends at the end and **sifts up** while the new value beats its parent; poll takes the root, moves the last element to the root and **sifts down** while a child beats it. Both are O(log n); peek is O(1); remove(Object) is O(n) because it must first find the element.

A heap only orders each parent against its children. The array is therefore *not* sorted: after offering 5, 3, 8, 1 into a min-queue, toString() prints [1, 3, 8, 5], and iterating a PriorityQueue does not give sorted order. Use repeated poll() to read values in priority order. The animation reproduces this array exactly; it is the same layout as the real class.

1Comparator<Integer> cmp = Comparator.naturalOrder();   // Comparator.reverseOrder() makes a max-queue
2PriorityQueue<Integer> pq = new PriorityQueue<>(cmp);
3pq.offer(x);              // append at the end, then sift up
4Integer top = pq.poll();  // last element to the root, then sift down
5Integer next = pq.peek(); // the root only; nothing is removed

With no comparator, PriorityQueue<Integer> is a **min-queue**: the smallest number leaves first, because natural order sorts small values first. The root of the heap is the smallest value, so peek() returns the minimum in O(1).

Use a min-queue whenever you repeatedly need the smallest remaining item: the k largest values (keep a min-queue of size k), merging sorted lists, Dijkstra's shortest paths.

1static List<Integer> sortedPolls(int[] values) {
2    PriorityQueue<Integer> pq = new PriorityQueue<>();
3    for (int v : values) pq.offer(v);
4    List<Integer> out = new ArrayList<>();
5    while (!pq.isEmpty()) out.add(pq.poll());        // ascending: n polls of O(log n) each
6    return out;
7}

1Comparator<Integer> cmp = Comparator.naturalOrder();   // Comparator.reverseOrder() makes a max-queue
2PriorityQueue<Integer> pq = new PriorityQueue<>(cmp);
3pq.offer(x);              // append at the end, then sift up
4Integer top = pq.poll();  // last element to the root, then sift down
5Integer next = pq.peek(); // the root only; nothing is removed

To get the largest value first, reverse the order: new PriorityQueue<>(Comparator.reverseOrder()) (or Collections.reverseOrder()). Choose “Max-queue” in the animation: the root is now the largest value and every comparison flips.

Do not write the comparator as (a, b) -> b - a. The subtraction overflows for values far apart: with Integer.MIN_VALUE, 1 and Integer.MAX_VALUE such a queue polls them in the order −2147483648, 2147483647, 1, which is not descending. Use Integer.compare(b, a) or Comparator.reverseOrder().

1static PriorityQueue<Integer> maxQueue() {
2    return new PriorityQueue<>(Comparator.reverseOrder());          // safe
3}
4static PriorityQueue<Integer> alsoSafe() {
5    return new PriorityQueue<>((a, b) -> Integer.compare(b, a));     // never subtract
6}

1Comparator<Integer> cmp = Comparator.naturalOrder();   // Comparator.reverseOrder() makes a max-queue
2PriorityQueue<Integer> pq = new PriorityQueue<>(cmp);
3pq.offer(x);              // append at the end, then sift up
4Integer top = pq.poll();  // last element to the root, then sift down
5Integer next = pq.peek(); // the root only; nothing is removed

A priority queue happily stores equal priorities. What it does *not* promise is FIFO order among them: PriorityQueue is not stable. Offering tasks a, b, c, d, e, f with priorities 2, 1, 2, 1, 2, 1 and polling them returns b d f a e c: the priority-1 tasks come first, but among the priority-2 tasks the order a, e, c differs from the arrival order a, c, e.

If equal priorities must be served in arrival order, add a tie-breaker to the comparator, usually an increasing sequence number. With a secondary comparison on the name the order becomes the fully determined b d f a c e.

Choose the “Duplicates” preset to see equal values sift without swapping: a tie never moves a node, which is exactly why order among equals is arbitrary.

1record Task(int priority, String name) {}
2
3static String drain(boolean tieBreak) {
4    Comparator<Task> byPriority = Comparator.comparingInt(Task::priority);
5    PriorityQueue<Task> pq = new PriorityQueue<>(tieBreak ? byPriority.thenComparing(Task::name) : byPriority);
6    String[] names = {"a", "b", "c", "d", "e", "f"};
7    int[] priority = {2, 1, 2, 1, 2, 1};
8    for (int i = 0; i < names.length; i++) pq.offer(new Task(priority[i], names[i]));
9    StringBuilder sb = new StringBuilder();
10    while (!pq.isEmpty()) sb.append(pq.poll().name());
11    return sb.toString();                          // drain(false) = "bdfaec", drain(true) = "bdface"
12}

1Comparator<Integer> cmp = Comparator.naturalOrder();   // Comparator.reverseOrder() makes a max-queue
2PriorityQueue<Integer> pq = new PriorityQueue<>(cmp);
3pq.offer(x);              // append at the end, then sift up
4Integer top = pq.poll();  // last element to the root, then sift down
5Integer next = pq.peek(); // the root only; nothing is removed

For your own classes, either implement Comparable<T> (one natural order) or pass a Comparator<T> to the constructor (any number of orders, chosen at the call site). Records and Comparator.comparingInt(...).thenComparing(...) make this short and readable.

The comparator must only use fields that do not change while the object sits in the queue. If a priority changes, the heap is not told: remove and re-insert the element instead (an O(n) remove plus an O(log n) offer), or use a lazy approach where stale entries are skipped when polled.

1record Job(String name, int priority, long createdAt) {}
2
3static PriorityQueue<Job> jobQueue() {
4    return new PriorityQueue<>(
5        Comparator.comparingInt(Job::priority).reversed()          // higher priority first
6                  .thenComparingLong(Job::createdAt));             // equal priority: older first
7}