What is a Java priority queue?
A Java priority queue is a data structure that orders elements by importance rather than by arrival time. This page covers what a priority queue is, how the java.util.PriorityQueue class works, how priority queues relate to the heap data structure, and how to share one across multiple servers using Valkey or Redis.
What is a priority queue?
An ordinary queue works on a "first in, first out" (FIFO) basis. Elements are processed in the order they arrived: work is always taken from the head of the queue, and new elements are added at the tail. Real life is full of FIFO queues, from people waiting for the next available cashier to cars traveling along a one-way road.
A priority queue is a queue in which every element carries a priority. Elements with higher priority are processed before elements with lower priority, regardless of when they were added. The head of the queue is always the highest-priority element, and once it is removed the queue reorganizes so that the next highest-priority element takes its place.
A common use case is handling the most valuable work first. Suppose a business wants to answer support requests from its biggest customers first. It can insert each request into a priority queue keyed on how much that customer has spent. When an agent becomes free, they take the head of the queue and get the most valuable request waiting, even if it arrived last.
How Java priority queues work
In Java, priority queues are implemented by the java.util.PriorityQueue class. By default, elements are ordered according to their natural ordering, meaning the class must implement Comparable. Alternatively, a Comparator can be supplied to the constructor to define the ordering explicitly.
These are the methods developers reach for most often:
- add(): Inserts the given element into the priority queue.
- offer(): Inserts the given element into the priority queue. Because java.util.PriorityQueue is unbounded, add() and offer() behave identically here; the two differ only on capacity-restricted queues, where add() throws an IllegalStateException and offer() returns false.
- peek(): Returns, but does not remove, the element at the head of the priority queue, or null if the queue is empty.
- poll(): Returns and removes the element at the head of the priority queue, or null if the queue is empty.
- remove(Object): Removes the given element from the queue, if it is present. The no-argument remove() removes the head instead, and throws a NoSuchElementException when the queue is empty.
- contains(): Returns true if the priority queue contains the given element.
- size(): Returns the number of elements in the queue.
- clear(): Removes all elements from the priority queue.
Two behaviours regularly catch developers out. First, java.util.PriorityQueue is not thread-safe; concurrent code should use java.util.concurrent.PriorityBlockingQueue instead. Second, iterating over a priority queue does not return elements in priority order. Only the head is guaranteed to be correct, so sorted output requires repeated calls to poll().
Priority queue vs heap: what is the difference?
The two terms are often used interchangeably, but they describe different things. A priority queue is an abstract data type: a contract describing behaviour, namely that removal always returns the highest-priority element. A heap is a concrete data structure: a tree in which every parent compares ahead of its children.
Heaps are simply the most practical way to implement that contract, which is why the two are so closely associated. java.util.PriorityQueue is backed by a binary heap. A priority queue could equally be built on a sorted list or a balanced tree, but a binary heap gives the best balance of insertion and removal cost.
That backing structure determines the performance of java.util.PriorityQueue:
| Operation | Time complexity |
|---|---|
offer(), add() | O(log n) |
poll(), remove() of the head | O(log n) |
peek(), size() | O(1) |
remove(Object), contains() | O(n) |
These figures describe the in-memory java.util.PriorityQueue class. A distributed priority queue stored in Valkey or Redis has different characteristics, since each operation involves a network round trip and server-side work.
Java priority queues in Valkey and Redis
A java.util.PriorityQueue lives inside a single JVM. As soon as an application runs across several instances, each one holds its own separate copy, and there is no shared view of what should be processed next. Moving the queue into a shared data store solves this.
Valkey and Redis are in-memory data structure stores commonly used for key-value databases, caches, and message brokers. Between them the available data types cover strings, hashes, lists, sets, sorted sets, streams, bitmaps and more, but none of them is a priority queue. Lists preserve insertion order only, so LPUSH and RPOP cannot express priority on their own.
The usual manual workaround is a sorted set, using the priority as the score and popping the lowest or highest scoring member with ZPOPMIN or ZPOPMAX. That works, but it leaves you to hand-roll serialization, comparator logic, and blocking consumers yourself.
Redisson removes that work by exposing the queue as a familiar Java interface. RPriorityQueue implements java.util.Queue and stores its contents in Valkey or Redis, so every application instance sees the same queue:
public class Task implements Comparable<Task>, Serializable {
private String name;
private int priority;
public Task(String name, int priority) {
this.name = name;
this.priority = priority;
}
// a lower number means a higher priority
@Override
public int compareTo(Task other) {
return Integer.compare(this.priority, other.priority);
}
public String getName() {
return name;
}
}
RPriorityQueue<Task> queue = redisson.getPriorityQueue("tasks");
queue.add(new Task("send-receipt", 5));
queue.add(new Task("charge-card", 1));
queue.add(new Task("update-analytics", 9));
Task first = queue.poll(); // charge-card
Task second = queue.poll(); // send-receipt
Task third = queue.poll(); // update-analytics
Elements are added in arbitrary order and come back out by priority, exactly as they would from the standard class, except that the ordering is shared by every process connected to the same Valkey or Redis instance.
Priority queue variants in Redisson
Redisson provides several priority queue objects, each mapping onto a standard Java interface:
| Redisson object | Java interface | Use when |
|---|---|---|
RPriorityQueue | Queue | Basic priority ordering is all you need |
RPriorityDeque | Deque | You need access at both ends of the queue |
RPriorityBlockingQueue | BlockingQueue | Consumers should block until work arrives |
RPriorityBlockingDeque | BlockingDeque | You need blocking consumers and both ends |
Configuration details for each object are covered in the Redisson queues documentation. For a worked comparison of these objects against sorted sets, and how to add acknowledgments and retries, see distributed priority queues in Java.
Ordering alone is often not enough for production job processing, which usually also needs acknowledgments, retry limits, and somewhere for failed work to go. The Reliable Queue in Redisson PRO assigns each message a priority from 0 (lowest) to 9 (highest) alongside acknowledgments, visibility timeouts, delivery limits, message delay, and a dead-letter queue. See All about Reliable Queue for Valkey and Redis for a full walkthrough.
Frequently asked questions
Is a priority queue the same as a heap?
No. A priority queue is an abstract data type describing behaviour, while a heap is a concrete data structure. Heaps are the most common way to implement priority queues, and java.util.PriorityQueue is backed by a binary heap, but the two terms are not interchangeable.
Is java.util.PriorityQueue thread-safe?
No. Use java.util.concurrent.PriorityBlockingQueue for concurrent access within a single JVM, or a Redisson priority queue when the queue must be shared across processes and machines.
Do Valkey and Redis have a native priority queue?
No. Lists are FIFO only. Priority ordering is usually built on sorted sets, where the score acts as the priority, or provided by a client library such as Redisson.
Can a priority queue be shared across multiple servers?
Not with java.util.PriorityQueue, which exists only in the heap memory of one JVM. Storing the queue in Valkey or Redis gives every application instance a single shared view of what to process next.