PriorityQueue Class in Java - Quiz

PriorityQueue stores its elements in an Object[] array organised as a binary heap: every element is no greater than its children. For the element at index i, the children are at 2*i + 1 and 2*i + 2 and the parent is at (i - 1) / 2, so the smallest element is always in cell 0 — the head of the queue. Such a heap is a min-heap; with a reverse-order comparator the largest element is on top — a max-heap.

On offer() the new element is written to the end of the array and sifts up, swapping with its parent while the parent is greater. On poll() the last element takes the place of the head and sifts down. Both operations follow at most one root-to-leaf path — O(log n). Siblings are not ordered: after offer(5, 1, 4, 2, 3) the array is [1, 2, 4, 5, 3].

• offer()/add(), poll()/remove() — O(log n): the element sifts up or down along one path of the heap.
• peek()/element(), size(), isEmpty() — O(1): the head is always in cell 0.
• contains(Object) and remove(Object) — O(n): the heap is not ordered for searching, so the whole array is scanned. remove(Object) compares with equals(), not with the comparator.
• addAll(c) adds elements one by one — O(m log n); the PriorityQueue(c) constructor builds the heap at once in O(n).

For the same reason the minimum of a min-heap is available in O(1), while the maximum takes O(n) to find: it can be in any leaf, and there are about n/2 leaves. If both ends are needed, keep two heaps or use a TreeSet.

The iterator, for-each, toString() and toArray() walk the internal heap array, so the order does not match the priority order: after offer(5, 1, 4, 2, 3) a for-each loop prints 1 2 4 5 3. Only the first element — the head — is guaranteed.

There are two ways to get sorted order:

• repeated poll() calls — the order is correct, but the queue is emptied;
• sorting a copy: pq.stream().sorted().toList() (the queue is left untouched). For a queue with a comparator use pq.stream().sorted(pq.comparator()); with natural ordering comparator() returns null and sorted(null) throws NullPointerException, so plain sorted() is needed there.

The element class must implement Comparable, or a Comparator is passed to the constructor:

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

Otherwise the code compiles, but offer() throws ClassCastException (on JDK 11+ already for the first element). int[] arrays are not Comparable either: new PriorityQueue<int[]>((a, b) -> Integer.compare(a[1], b[1])).

A max-heap is a reverse-order comparator: new PriorityQueue<>(Collections.reverseOrder()) or Comparator.comparingInt(Task::priority).reversed(). Avoid (a, b) -> b - a: the subtraction overflows on large numbers; the safe form is (a, b) -> Integer.compare(b, a).

The order of elements with equal priority is not guaranteed: the heap is not stable. If you need FIFO among equals, add a sequence number as a second criterion: .thenComparingLong(Task::seq).

Changing priority. The heap is rebuilt only on offer() and poll(), so it does not notice a change to the field the objects are compared by — the extraction order becomes wrong. There is no “update priority” method: remove the object (remove(obj), O(n)), change the field and add it again. It is safer to make the compared fields immutable, for example with a record.

Size. The number in the constructor is only the initial capacity (11 by default, less than 1 — IllegalArgumentException); the array grows by itself and offer() always returns true. A limit is written by hand: after offer() check size() and call poll() — this is how the k largest elements are found in O(n log k).

Threads. PriorityQueue is not synchronized; concurrent offer() and poll() calls can corrupt the heap. The thread-safe counterpart is java.util.concurrent.PriorityBlockingQueue with a blocking take().

Both collections order elements with Comparable or a Comparator, but they are built differently:

• Structure: PriorityQueue is a binary heap on a single array; TreeSet is a red-black tree (a TreeMap inside) with a node per element.
• Duplicates: PriorityQueue keeps them; TreeSet does not add an element for which the comparator returned 0.
• Access: PriorityQueue gives only the head (peek() in O(1)); TreeSet gives both ends and neighbours (first(), last(), ceiling(), floor()) in O(log n).
• Iteration: the PriorityQueue iterator does not sort; TreeSet iterates in sorted order.
• Finding and removing an element: O(n) versus O(log n).

Pick PriorityQueue for priority processing, schedulers, top-k and graph algorithms; pick TreeSet for unique sorted values, ranges, and cases where you need both the minimum and the maximum.