Java Reference ยท Collections
The PriorityQueue class
Reference for java.util.PriorityQueue: a binary-heap queue that always returns the smallest element, with Comparator ordering, complexity and pitfalls.
PriorityQueue<E> is an unbounded queue backed by a binary min-heap. peek() and poll() always give you the element that is smallest according to its ordering, no matter in which order elements were added. This is the natural structure for schedulers, "top k" problems and Dijkstra-style algorithms.
Ordering comes from the elements' natural order (Comparable) or from a Comparator passed to the constructor. For the largest element first, pass a reversed comparator.
PriorityQueue<Integer> min = new PriorityQueue<>(); PriorityQueue<Integer> max = new PriorityQueue<>(Comparator.reverseOrder());
Try it
Press Run (or Ctrl + Enter) to see the result here.
Program input ยท what you'd type while the program runs
Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.
Press Run (or Ctrl + Enter) to see the result here.
Program input ยท what you'd type while the program runs
Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.
Syntax
public class PriorityQueue<E> extends AbstractQueue<E> implements java.io.Serializable
| Constructor | Description |
|---|---|
PriorityQueue() |
Natural ordering, initial capacity 11. |
PriorityQueue(int initialCapacity) |
Natural ordering, given initial capacity (must be at least 1). |
PriorityQueue(Comparator<? super E> c) |
Ordering from the comparator. |
PriorityQueue(int initialCapacity, Comparator<? super E> c) |
Both. |
PriorityQueue(Collection<? extends E> c) |
Heap built from a collection (keeps the ordering of a SortedSet or another PriorityQueue). |
Throws: NullPointerException for a null element; ClassCastException when an element is not Comparable and no comparator was given.
Usage notes
- Complexity:
offerandpollareO(log n),peekisO(1),remove(Object)andcontainsareO(n). - Iteration is not sorted.
toString(), the iterator and streams show the heap's internal array order. Onlypoll()yields sorted order. To get a sorted list, poll repeatedly or sort a copy. - Ties have no guaranteed order; elements that compare as equal can come out in any order. Add a tie-breaker (a sequence number or a second comparator) if you need stability.
- Do not mutate an element's priority while it is inside the queue. The heap will not notice. Remove it, change it, and add it again.
- No nulls, and the comparator must be consistent.
- Max-heap: use
Comparator.reverseOrder(). Avoid(a, b) -> b - a, which overflows for large values; useInteger.compare(b, a). - Not thread-safe. Use
PriorityBlockingQueueacross threads. - Top-k pattern: keep a min-heap of size k to track the k largest values in
O(n log k).