What is a Java priority queue?
A Java priority queue is a highly useful data structure that organizes elements according to their priority. But what is a Java priority queue exactly, and how do Java priority queues work?
What are Java priority queues?
In computer science, a queue is a data structure that operates according to the “first in, first out” (FIFO) philosophy. Elements in the queue are processed in the order in which they arrived: we always process the element at the “head” (front) of the queue, and new elements are inserted at the “tail” (back) of the queue. The world around us is full of queues in real life, from people waiting for the next available cashier to cars traveling on a one-way road.
A priority queue is a special kind of queue in which each element is assigned a given priority. Elements that have higher priorities are processed before elements with lower priorities. The element at the head of the priority queue is guaranteed to have the highest priority of all the elements in the queue. Once we “pop” (i.e. remove) the head of the priority queue, the queue reorganizes itself to place the element with the next highest priority at its head.
One of the most common use cases of priority queues is finding the most important or valuable items. For example, suppose that a business wants to answer customer support requests starting with their most valuable customers. The business could insert each customer into a priority queue, where the priority is the amount of money that the customer has spent so far with the business. When a customer support agent becomes available, he or she can then pop the head of the queue, representing the most valuable customer with a request.
In Java, priority queues are implemented using the java.util.PriorityQueue class. The elements in a Java priority queue are ordered according to their natural ordering. Developers can use a Comparator to define how the priority queue compares two different elements.
How do Java priority queues work?
The java.util.PriorityQueue class defines the methods that developers need to know when working with priority queues in Java. Below are some of the most important methods of Java priority queues:
- add(): Inserts the given element into the priority queue.
- clear(): Removes all of the elements from the priority queue.
- contains(): Returns true if the priority queue contains the given element.
- offer(): Inserts the given element into the priority queue. This method’s behavior is identical to add() except when the queue is full: add() will throw an IllegalStateException, while offer() will return 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(): Removes the given element from the queue, if it is present.
- size(): Returns the number of elements in the queue.
Java priority queues in Redis
Redis is an open-source, in-memory data structure store used to create NoSQL key-value databases, caches, and message brokers. However, Redis doesn’t include a wide variety of data structures—only lists, sets, sorted sets, hashes, and strings.
It is possible to implement a priority queue in Redis using lists and the LPUSH/RPUSH/LPOP/RPOP operations. However, this requires extra work and can be tricky for developers who are new to the Redis project.
To lower the Redis learning curve, many Java developers are installing third-party Redis Java libraries such as Redisson. Redisson contains many familiar Java objects, collections, and constructs for Java developers working with Redis.
Redisson implements Java priority queues in Redis using the RPriorityQueue interface, which behaves very similarly to the original PriorityQueue class. Below is an example of how to use RPriorityQueue:
public class Entry implements Comparable<Entry>, Serializable {
private String key;
private Integer value;
public Entry(String key, Integer value) {
this.key = key;
this.value = value;
}
@Override
public int compareTo(Entry o) {
return key.compareTo(o.key);
}
}
RPriorityQueue<Entry> queue = redisson.getPriorityQueue("anyQueue");
queue.add(new Entry("b", 1));
queue.add(new Entry("c", 1));
queue.add(new Entry("a", 1));
// Entry [a:1]
Entry e = queue.poll();
// Entry [b:1]
Entry e = queue.poll();
// Entry [c:1]
Entry e = queue.poll();