Lesson 18.2 · Heaps and Priority Queues

PriorityQueue in Java

Java's PriorityQueue is a min-heap by default; pass a Comparator for a max-heap or to order arrays and objects.

10 min

Think of it like this

A to-do app with a "sort by" setting: the list is the same, but you decide what goes to the top: earliest deadline, highest priority, or shortest task.

1.The API you'll use

offer(x) adds, poll() removes and returns the top (null if empty), peek() looks at it, size() counts. Comparator.reverseOrder() makes a max-heap. For pairs, store int[] and compare a chosen index with Integer.compare (never a[1] - b[1], which overflows for large values).

Main.java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        PriorityQueue<Integer> min = new PriorityQueue<>();
        PriorityQueue<Integer> max = new PriorityQueue<>(Comparator.reverseOrder());
        for (int x : new int[]{5, 1, 8, 3}) { min.offer(x); max.offer(x); }
        System.out.println(min.peek() + " " + max.peek());

        StringBuilder sb = new StringBuilder();
        while (!min.isEmpty()) sb.append(min.poll()).append(' ');
        System.out.println(sb.toString().trim());          // polling gives sorted order
        System.out.println(max);                            // printing shows the internal array

        PriorityQueue<int[]> byDistance = new PriorityQueue<>((a, b) -> Integer.compare(a[1], b[1]));
        byDistance.offer(new int[]{1, 30});
        byDistance.offer(new int[]{2, 10});
        byDistance.offer(new int[]{3, 20});
        System.out.println("closest id: " + byDistance.poll()[0]);
    }
}

Output

1 8
1 3 5 8
[8, 3, 5, 1]
closest id: 2

Remember

Default is a min-heap.
Comparator.reverseOrder() for max.
Integer.compare, not subtraction.

Common mistakes

Printing a PriorityQueue and assuming it's sorted.
Subtraction comparators overflowing.

Command Palette

PriorityQueue in Java

1.The API you'll use