A heap is a tree-shaped structure that keeps the most important value at its root. In a min-heap, a parent is no larger than its children. In a max-heap, a parent is no smaller. Unlike a binary search tree, a heap does not separate every smaller key into a left subtree.
Java's PriorityQueue uses a priority heap. It lets you inspect or remove the smallest element under natural ordering, or the element that comes first under a supplied comparator. That makes it useful for scheduling work, selecting small values and processing items by urgency.
Priority order versus arrival order
An ordinary FIFO queue removes items in their arrival order. A priority queue removes items according to its ordering rule. If waiting jobs have durations 12, 4 and 9, a queue ordered by shortest duration retrieves 4 even though 12 arrived first.
PriorityQueue does not automatically understand what a high business priority means. With natural integer ordering, the smallest number comes first. If your application labels more urgent work with larger numbers, use a reverse comparator rather than expecting the name of the collection to imply descending order.
There is also a distinction between retrieving the next item and inspecting the entire collection. The heap guarantees its head according to priority. It does not keep the iterator, printed representation or backing array fully sorted. Obtain sorted removal order by repeatedly polling the queue.
What the binary heap stores
A binary heap is commonly stored in an array as a complete binary tree. Complete means every level is full except possibly the last, whose nodes fill from left to right. It does not mean the number of elements must be a power of two.
For a zero-based index i, a node's children are at 2*i+1 and 2*i+2 when those positions exist. Its parent, for i greater than zero, is at (i-1)/2 using integer division. These formulas avoid storing separate child-reference objects.
Insertion places a new item at the end, then moves it upward while the ordering rule is violated. Removing the root moves the final element to the root, then moves it downward as needed. These movements restore a partial ordering, not a complete sort of the array.
You can implement these operations to learn heap mechanics, but ordinary Java applications usually need PriorityQueue's established behavior rather than another handwritten heap.
Ordering objects and resolving ties
A custom comparator can order tasks by a field such as deadline or estimated duration. Compare the relevant values with Integer.compare or Comparator.comparingInt. Subtracting two arbitrary integers as a comparison can overflow and reverse the result.
If two elements compare as equal, PriorityQueue does not promise their insertion order will be preserved. Add a secondary comparison when a consistent tie rule matters. An arrival sequence number can give equal-priority tasks an explicit FIFO tie-breaker.
Avoid changing a field used by the comparator while its object remains in the queue. The heap will not notice that mutation and rearrange itself automatically. Remove the entry, change its priority, and offer it again, or design immutable task records with replacement entries.
Operation costs and choosing alternatives
For n entries, offer and poll generally take O(log n) time because an element moves along the heap's height. peek takes O(1) time. Searching for an arbitrary entry with contains, or removing it by value, takes O(n) time in PriorityQueue.
A heap therefore fits repeated best-next retrieval. It is less suitable for frequent lookup by identifier or for producing a sorted range of keys. A HashMap supports key-based lookup; a TreeMap supports ordered keys and range operations. The BST lesson explains that distinction.
PriorityQueue allows duplicate elements but rejects null. The null returned by peek or poll on an empty queue therefore cannot be confused with a stored null entry. The exception-throwing counterparts element and remove can be appropriate when emptiness signals a programming error.
The collection is not thread-safe. Sharing it among workers requires a suitable concurrency design; PriorityBlockingQueue offers a concurrent priority queue with different blocking behavior. Merely replacing the collection does not solve starvation when urgent tasks continually delay ordinary work.
Heaps and Priority Queues Summary
- A heap maintains a priority head through partial ordering.
- Default integer PriorityQueue behavior is a min-heap.
- Use comparators for descending values or object priorities.
- Add explicit tie-breakers when deterministic equal-priority order matters.
- Continue with graphs to apply queues to traversal.
Heaps and Priority Queues Examples
Each example shows the code, the output it produces and what each part does.
A min-heap of repair durations
Save this complete program as RepairQueueExample.java.
Calling peek twice would return the same head because neither call consumes an element. Calling poll twice would remove two entries. Choose the operation according to whether the next stage merely needs to inspect work or actually begins processing it.
import java.util.PriorityQueue;
public class RepairQueueExample {
public static void main(String[] args) {
PriorityQueue<Integer> minutes = new PriorityQueue<>();
minutes.offer(12);
minutes.offer(4);
minutes.offer(9);
System.out.println("Next: " + minutes.peek());
while (!minutes.isEmpty()) {
System.out.println(minutes.poll());
}
System.out.println("Empty: " + minutes.peek());
}
}Next: 4
4
9
12
Empty: nullLine-by-line explanation
- Lines 5 to 8The default integer queue orders durations from smallest to largest.
- Line 9peek returns four without removing it.
- Lines 10 to 12poll removes one head per iteration, exposing the next smallest duration.
- Line 13peek returns null after the queue has been drained.
Creating a max-heap ordering
Reverse ordering makes the largest score the head.
Reversing the comparator affects future heap operations throughout this queue. It is different from reversing a printed list after the fact. Decide the ordering when constructing the queue so offer and poll agree about priority.
import java.util.Comparator;
import java.util.PriorityQueue;
public class ScoreQueueExample {
public static void main(String[] args) {
PriorityQueue<Integer> scores =
new PriorityQueue<>(Comparator.reverseOrder());
scores.offer(18);
scores.offer(31);
scores.offer(24);
while (!scores.isEmpty()) {
System.out.println(scores.poll());
}
}
}31
24
18Line-by-line explanation
- Lines 6 to 7The reverse comparator changes which integer is considered first.
- Lines 8 to 10Insertion order remains 18, 31, 24; retrieval order follows priority.
- Lines 11 to 12Each removal yields the greatest remaining score.
Scheduling jobs with an explicit tie-breaker
Two jobs have equal durations, so their sequence numbers decide their order.
import java.util.Comparator;
import java.util.PriorityQueue;
public class JobQueueExample {
record Job(String name, int minutes, int sequence) {}
public static void main(String[] args) {
Comparator<Job> order = Comparator.comparingInt(Job::minutes)
.thenComparingInt(Job::sequence);
PriorityQueue<Job> jobs = new PriorityQueue<>(order);
jobs.offer(new Job("screen", 8, 0));
jobs.offer(new Job("hinge", 3, 1));
jobs.offer(new Job("strap", 3, 2));
while (!jobs.isEmpty()) {
System.out.println(jobs.poll().name());
}
}
}hinge
strap
screenLine-by-line explanation
- Line 5An immutable Java 17 record keeps the comparison fields from changing.
- Lines 8 to 9Duration is the primary key; sequence breaks equal-duration ties.
- Lines 11 to 13The first arrival is not necessarily the first removal, because screen takes longer.
- Lines 14 to 15Both three-minute jobs are returned before the eight-minute job, in their explicit sequence order.
Heaps and Priority Queues FAQ
Does printing a PriorityQueue show sorted values?
No. Its string representation follows iteration, whose order is unspecified. Poll a copy if you need sorted display without consuming the original.
Can a priority queue solve shortest-path problems?
It can select the next candidate in algorithms such as Dijkstra's algorithm. You still need distances, edge rules and careful handling of outdated entries; the queue alone does not compute a route.
Is Java's PriorityQueue a min-heap or a max-heap?
A min-heap by default: poll() returns the smallest element according to natural ordering. For a max-heap, pass a reversed comparator, new PriorityQueue<>(Comparator.reverseOrder()), or a comparator built with .reversed() for objects.
How do I find the k largest values efficiently?
Keep a min-heap of at most k elements. Add each value, and when the heap grows past k, poll the smallest. At the end the heap holds the k largest values, and the work is O(n log k), which beats sorting everything when k is much smaller than n.
Is PriorityQueue thread-safe?
No. For a priority queue shared between threads, use PriorityBlockingQueue from java.util.concurrent, whose take() also waits until an element is available. Like PriorityQueue, its iteration order isn't sorted.
Heaps and Priority Queues Exercises
Answer each one and check it instantly. If you get stuck, open the hint before the answer.
A natural-order integer queue contains 15, 6 and 10. What does peek return?
Two jobs compare as equal and the comparator has no tie-breaker. What can you assume?
Heaps and Priority Queues Quiz
2 questions to check what you learned.
Which method retrieves and removes the current priority head?
- poll()
- peek()
- iterator()
Why is changing a queued object's priority field dangerous?
- The heap does not automatically restore ordering after the mutation
- Java always prevents the field from changing
- PriorityQueue turns the object into a copy