Java PriorityQueue

With no comparator, a PriorityQueue orders its elements by their natural order (Comparable), so elements must implement Comparable or construction fails at the first insertion. With a Comparator, the comparator decides, and it also decides which elements count as equal. Build comparators with Comparator.comparingInt(...), reversed() and thenComparing(...).

The queue below holds strings: by natural order apple is first; by length fig is first. Equal-priority elements come out in **no guaranteed order**, since a heap is not stable; add a sequence number to the comparator if arrival order must break ties.

1static void orderings() {
2    PriorityQueue<String> natural = new PriorityQueue<>(List.of("pear", "fig", "apple"));
3    System.out.println(natural.poll());          // apple: alphabetical order
4    PriorityQueue<String> byLength = new PriorityQueue<>(Comparator.comparingInt(String::length));
5    byLength.addAll(List.of("pear", "fig", "apple"));
6    System.out.println(byLength.poll());         // fig: the shortest string
7}

A PriorityQueue is a **min-heap**: peek and poll return the smallest element. Its toString and iterator expose the underlying **heap array**, not sorted order: after adding 5, 3, 8 and 1 it prints [1, 3, 8, 5], while polling gives 1, 3, 5, 8. To get sorted output, poll repeatedly (O(n log n) in all).

Costs from the documentation: offer, add, poll, remove() and peek and element are O(log n), O(log n), O(log n), O(log n) and O(1); contains and remove(Object) are O(n). Passing a collection to the constructor builds the heap in O(n).

1static void minHeapDefault() {
2    PriorityQueue<Integer> pq = new PriorityQueue<>();
3    for (int x : new int[]{5, 3, 8, 1}) pq.add(x);
4    System.out.println(pq);                      // [1, 3, 8, 5]: the heap array, not sorted
5    System.out.println(pq.peek());               // 1
6    StringBuilder sb = new StringBuilder();
7    while (!pq.isEmpty()) sb.append(pq.poll()).append(' ');
8    System.out.println(sb.toString().trim());    // 1 3 5 8
9}

For a **max-heap**, pass Collections.reverseOrder() or Comparator.reverseOrder() (natural order reversed), or Comparator.comparingInt(f).reversed() for a field. Do not write (a, b) -> b - a: the subtraction **overflows** when the values are far apart, and the heap silently misorders them.

With the values 1 and Integer.MIN_VALUE the subtraction version considers 1 smaller, so it polls Integer.MIN_VALUE first, which is wrong for a max-heap. Use Integer.compare(b, a) if a lambda is needed.

1static void maxHeap() {
2    PriorityQueue<Integer> good = new PriorityQueue<>(Collections.reverseOrder());
3    good.addAll(List.of(1, Integer.MIN_VALUE, 7));
4    System.out.println(good.poll());             // 7: the largest first
5
6    PriorityQueue<Integer> broken = new PriorityQueue<>((a, b) -> b - a);   // overflows near the limits
7    broken.addAll(List.of(1, Integer.MIN_VALUE));
8    System.out.println(broken.poll());           // -2147483648: wrong, the smaller value came out first
9
10    PriorityQueue<Integer> fixed = new PriorityQueue<>((a, b) -> Integer.compare(b, a));
11    fixed.addAll(List.of(1, Integer.MIN_VALUE));
12    System.out.println(fixed.poll());            // 1
13}

PriorityQueue.remove(Object) and contains(Object) do a **linear scan** with equals, not the comparator, so they cost O(n) and can disagree with the ordering: with a comparator that ranks by length, the queue holding "aa" does not contain "bb" although the comparator treats them as equal. There is also no decreaseKey and no way to find an element's position.

Workarounds: use **lazy deletion** (mark removed items and skip them when polled, as in Dijkstra and the sliding median), re-insert an updated copy and skip the stale one, use a TreeSet (O(log n) removal and neighbours, with a unique tiebreaker in the comparator), or write an **indexed priority queue**.

1static void arbitraryRemoval() {
2    PriorityQueue<String> pq = new PriorityQueue<>(Comparator.comparingInt(String::length));
3    pq.add("aa"); pq.add("c"); pq.add("bbb");
4    System.out.println(pq.contains("zz"));       // false: contains() uses equals, not the comparator
5    System.out.println(pq.remove("zz"));         // false: nothing removed
6    System.out.println(pq.remove("c"));          // true, found by a linear scan
7    System.out.println(pq.poll());               // aa
8}