Java priority queue pop

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, 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 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  Entry e = queue.poll();

Источник

Java priority queue pop

An unbounded priority queue based on a priority heap. The elements of the priority queue are ordered according to their natural ordering, or by a Comparator provided at queue construction time, depending on which constructor is used. A priority queue does not permit null elements. A priority queue relying on natural ordering also does not permit insertion of non-comparable objects (doing so may result in ClassCastException ). The head of this queue is the least element with respect to the specified ordering. If multiple elements are tied for least value, the head is one of those elements — ties are broken arbitrarily. The queue retrieval operations poll , remove , peek , and element access the element at the head of the queue. A priority queue is unbounded, but has an internal capacity governing the size of an array used to store the elements on the queue. It is always at least as large as the queue size. As elements are added to a priority queue, its capacity grows automatically. The details of the growth policy are not specified. This class and its iterator implement all of the optional methods of the Collection and Iterator interfaces. The Iterator provided in method iterator() is not guaranteed to traverse the elements of the priority queue in any particular order. If you need ordered traversal, consider using Arrays.sort(pq.toArray()) . Note that this implementation is not synchronized. Multiple threads should not access a PriorityQueue instance concurrently if any of the threads modifies the queue. Instead, use the thread-safe PriorityBlockingQueue class. Implementation note: this implementation provides O(log(n)) time for the enqueuing and dequeuing methods ( offer , poll , remove() and add ); linear time for the remove(Object) and contains(Object) methods; and constant time for the retrieval methods ( peek , element , and size ). This class is a member of the Java Collections Framework.

Constructor Summary

Creates a PriorityQueue with the default initial capacity (11) that orders its elements according to their natural ordering.

Creates a PriorityQueue with the default initial capacity and whose elements are ordered according to the specified comparator.

Creates a PriorityQueue with the specified initial capacity that orders its elements according to their natural ordering.

Creates a PriorityQueue with the specified initial capacity that orders its elements according to the specified comparator.

Method Summary

Returns the comparator used to order the elements in this queue, or null if this queue is sorted according to the natural ordering of its elements.

Returns an array containing all of the elements in this queue; the runtime type of the returned array is that of the specified array.

Methods inherited from class java.util.AbstractQueue

Methods inherited from class java.util.AbstractCollection

Methods inherited from class java.lang.Object

Methods inherited from interface java.util.Collection

Methods inherited from interface java.lang.Iterable

Constructor Detail

PriorityQueue

Creates a PriorityQueue with the default initial capacity (11) that orders its elements according to their natural ordering.

PriorityQueue

public PriorityQueue(int initialCapacity)

Creates a PriorityQueue with the specified initial capacity that orders its elements according to their natural ordering.

PriorityQueue

Creates a PriorityQueue with the default initial capacity and whose elements are ordered according to the specified comparator.

PriorityQueue

Creates a PriorityQueue with the specified initial capacity that orders its elements according to the specified comparator.

PriorityQueue

Creates a PriorityQueue containing the elements in the specified collection. If the specified collection is an instance of a SortedSet or is another PriorityQueue , this priority queue will be ordered according to the same ordering. Otherwise, this priority queue will be ordered according to the natural ordering of its elements.

PriorityQueue

Creates a PriorityQueue containing the elements in the specified priority queue. This priority queue will be ordered according to the same ordering as the given priority queue.

PriorityQueue

Creates a PriorityQueue containing the elements in the specified sorted set. This priority queue will be ordered according to the same ordering as the given sorted set.

Источник

Class PriorityQueue

An unbounded priority queue based on a priority heap. The elements of the priority queue are ordered according to their natural ordering, or by a Comparator provided at queue construction time, depending on which constructor is used. A priority queue does not permit null elements. A priority queue relying on natural ordering also does not permit insertion of non-comparable objects (doing so may result in ClassCastException ).

The head of this queue is the least element with respect to the specified ordering. If multiple elements are tied for least value, the head is one of those elements — ties are broken arbitrarily. The queue retrieval operations poll , remove , peek , and element access the element at the head of the queue.

A priority queue is unbounded, but has an internal capacity governing the size of an array used to store the elements on the queue. It is always at least as large as the queue size. As elements are added to a priority queue, its capacity grows automatically. The details of the growth policy are not specified.

This class and its iterator implement all of the optional methods of the Collection and Iterator interfaces. The Iterator provided in method iterator() and the Spliterator provided in method spliterator() are not guaranteed to traverse the elements of the priority queue in any particular order. If you need ordered traversal, consider using Arrays.sort(pq.toArray()) .

Note that this implementation is not synchronized. Multiple threads should not access a PriorityQueue instance concurrently if any of the threads modifies the queue. Instead, use the thread-safe PriorityBlockingQueue class.

Implementation note: this implementation provides O(log(n)) time for the enqueuing and dequeuing methods ( offer , poll , remove() and add ); linear time for the remove(Object) and contains(Object) methods; and constant time for the retrieval methods ( peek , element , and size ).

This class is a member of the Java Collections Framework.

Источник