PriorityQueue is a queue where the smallest element always comes out first, no matter the order you put things in. It's backed by a binary min-heap stored in an array, which gives O(log n) inserts and removals and O(1) access to the head. This lesson covers how the heap is laid out, the API you'll actually use, how to flip it into a max-heap with a Comparator, the gotchas around iteration order and null values, and the kinds of problems it suits well.

The Queue interface lesson covered the FIFO contract: first in, first out. PriorityQueue implements Queue, but it does not behave like one. The head of a PriorityQueue is whichever element is currently the smallest, not whichever one arrived first.

The difference in one program: A storefront tags incoming orders with a priority number, where a lower number means "process sooner". Prime orders are priority 1, expedited orders are priority 2, and standard orders are priority 3.

What happened: The orders went in as 3, 1, 2, 1, but they came out as 1, 1, 2, 3. The queue isn't replaying insertion order. Every time you call poll, the queue scans its internal structure for the current minimum and hands you that. The standard order (priority 3) waits behind both prime orders and the expedited one, even though it arrived first.

That ordering rule is what makes PriorityQueue useful. You add items as they come in, and you take them out in priority order without sorting anything yourself.

Internally, PriorityQueue stores its elements in an array, but it treats that array as a binary tree. The root of the tree (index 0) is always the smallest element. Every parent is smaller than or equal to its two children. That property is called the heap invariant, and it's what makes peek cheap and poll and offer logarithmic.

The mapping between the tree and the array uses simple index math. For a node at index i:

If you offer the values 5, 2, 8, 1, 3 one by one, the resulting heap looks like this:

The root holds 1, the smallest value. Every parent is at most as large as its children: 1 <= 2, 1 <= 8, 2 <= 5, 2 <= 3. The value 3 (at index 4) is smaller than 8 (at index 2), but they're in different subtrees. The heap property only cares about the parent-child relationship along a path, not about left-to-right order across the tree. This is why iterating over a heap doesn't give you sorted output.

The same tree lives in an array like this:

When you call offer(x), the new element goes to the next free slot at the end of the array, then "bubbles up" by swapping with its parent as long as it's smaller. When you call poll(), the root is removed, the last element is moved to the root, and it "sinks down" by swapping with its smaller child as long as the child is smaller. Each path from a leaf to the root has length log2(n), so both operations are O(log n).

offer and poll are O(log n) because of the bubble-up and sink-down walks. peek is O(1) because it just reads index 0. contains and remove(Object) are O(n) because the heap has no efficient way to find an arbitrary element.

The methods you'll use most of the time come from the Queue interface, plus the constructor:

A small example using all of them. The store keeps a queue of pending order IDs. The smaller the ID, the older the order, and the store wants to process the oldest first.

peek returns the current minimum (100) without removing it, which is why the size stayed at 4. Each poll removes and returns the current minimum and shrinks the queue by one. After two polls, the remaining values are 102 and 105, and the new minimum is 102.

There's also add and remove() (no argument) from the Queue interface, which behave like offer and poll but throw exceptions on failure instead of returning special values. For an unbounded PriorityQueue, add never fails, so offer and add end up doing the same thing. Stick to offer and poll for consistency, and let null be your "queue is empty" signal.

A common gotcha: iterating a PriorityQueue does not give you the elements in sorted order. The only element with a guaranteed position is the head.

The iteration order matches the array layout we saw earlier: 1, 2, 8, 5, 3. That's the order the heap stored the values, not sorted order. Only the very first element (1, the root) is guaranteed to be the minimum.

If you actually want sorted output, you have two options. Either poll the queue until it's empty (which gives you sorted order, but destroys the queue), or copy the elements out and sort them with Collections.sort or a TreeSet. There is no "give me a sorted view of this heap" method.

This shows up when printing a PriorityQueue for debugging:

The output is the array's internal order. It does not mean the heap is broken, and it does not mean the elements are unsorted in some meaningful sense. It just means iteration walks the array.

Pulling all elements out in sorted order is O(n log n) because each of the n polls is O(log n). That's the same complexity as Arrays.sort, but with the advantage that you can stop early after the first k elements.

The no-argument constructor we've been using gives you a min-heap using natural ordering, which is Comparable.compareTo on whatever element type you store. For Integer, that's numeric order. For String, that's lexicographic order. For your own classes, you need to either implement Comparable or supply a Comparator.

Two other constructors are useful:

The first lets you preallocate space if you know roughly how many elements you'll insert. The default capacity is 11, and the heap grows automatically when it fills up, so this is purely a performance optimization. The second takes a Comparator and uses it instead of natural ordering, which is how you turn a min-heap into a max-heap.

To get a max-heap, use Comparator.reverseOrder(). It reverses the natural ordering, so the "smallest" element by the comparator is actually the numerically largest one, and that's what sits at the head.

The comparator flips the ordering, so the head is always the largest value rather than the smallest. The product with the most units sold (310) sits at the head, and each poll returns the next largest value.

This is the pattern for "top-K" problems. To find the K most popular products, keep a min-heap of size K. For each new product, push it in; if the heap grows past K, pop the smallest. The smallest in the heap is always the K-th best seller, so anything smaller is correctly discarded. After scanning all products, the heap holds exactly the top K, and you can drain them out.

The min-heap holds the three largest values seen so far. When a new value arrives, it joins the heap; if that pushes the size past k, the smallest member gets evicted. The smallest in the heap acts as a threshold: any new value smaller than the heap's head can't beat the current top three.

We polled three times, and the values came out smallest-to-largest within the top three (175, 250, 310). That's the heap's natural min-first behavior, and it's what you want for top-K problems where the heap acts as a "cutoff" filter.

PriorityQueue rejects null elements. Trying to insert one throws NullPointerException, because the queue needs to compare every element against others to maintain the heap invariant, and null has no ordering.

The throw happens at the moment of insertion. The queue won't sit on a null and let you discover the problem later. That makes the failure easy to trace, but it also means you can't use null as a "no value yet" placeholder, the way you sometimes can with ArrayList or HashMap.

A related point: poll() and peek() return null to mean "the queue is empty". That's the only way null ever comes out of a PriorityQueue, and it's why the queue has to forbid null as an element. If null were a legal element, you couldn't tell the difference between "the head is null" and "the queue is empty".

If you'd rather have an exception on an empty queue, use element() and remove() instead. Both throw NoSuchElementException rather than returning null. Most code prefers the null-returning forms because they fit cleanly into a while (!pq.isEmpty()) loop.

Use PriorityQueue when the ordering you care about isn't insertion order, and you need cheap access to whichever element is "next" by some priority.

Three common scenarios:

Top-K queries. Find the K largest or smallest elements from a stream of data without sorting the whole thing. The earlier top-three-sellers example shows the shape: a min-heap of size K, evicting the smallest whenever the heap grows past K, gives you the K largest values in O(n log k) time.

Scheduling and event ordering. Process tasks in priority order, like routing prime orders ahead of standard ones, or running scheduled jobs in order of their next run time. The store can stuff every pending order into a PriorityQueue<Order> keyed by priority, and poll always hands back the most urgent one. This is the core of any "always work on the most important thing next" system.

Graph algorithms like Dijkstra's shortest path. Dijkstra's algorithm needs to repeatedly find the unvisited node with the smallest tentative distance. A min-heap keyed by distance gives that in O(log n) per step.

Skip PriorityQueue if you want FIFO behavior (use ArrayDeque or LinkedList), or if you need a fully sorted view of the elements at all times (use TreeSet for unique elements or sort an ArrayList once when you need the order). Also skip it when you need fast contains or fast remove(Object), since both walk the array linearly.

Building a heap from a known collection in one shot is O(n) using new PriorityQueue<>(collection), which is faster than offering each element one by one (O(n log n)). The constructor uses a "heapify" pass that's cheaper than n separate inserts.