Skip to content
Tutorials Center
My learning

Topics

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.

Java
PriorityQueue<Integer> min = new PriorityQueue<>();
PriorityQueue<Integer> max = new PriorityQueue<>(Comparator.reverseOrder());

Try it

Java Always the smallest first

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.

Java Tasks by priority and the iteration trap

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

Java
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: offer and poll are O(log n), peek is O(1), remove(Object) and contains are O(n).
  • Iteration is not sorted. toString(), the iterator and streams show the heap's internal array order. Only poll() 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; use Integer.compare(b, a).
  • Not thread-safe. Use PriorityBlockingQueue across threads.
  • Top-k pattern: keep a min-heap of size k to track the k largest values in O(n log k).