PriorityQueue is an unbounded Queue implementation inwards Java, which is based on priority heap. PriorityQueue allows you lot to proceed elements inwards a item order, according to in that place natural guild or custom guild defined by Comparator interface inwards Java. Head of priority queue information construction will e'er comprise to the lowest degree chemical constituent amongst observe to specified ordering. For example, inwards this post, nosotros volition exercise a PriorityQueue of Items, which are ordered based upon in that place price, this volition allow us to procedure Items, starting from lowest price. Priority queue is besides really useful inwards implementing Dijkstra algorithm inwards Java. You tin utilisation to PriorityQueue to proceed unsettled nodes for processing. One of the key affair to cry upwards nearly PriorityQueue inwards Java is that it's Iterator doesn't guarantee whatever order, if you lot desire to traverse inwards ordered fashion, meliorate utilisation Arrays.sort(pq.toArray()) method. PriorityQueue is besides not synchronized, which agency tin non hold upwards shared safely betwixt multiple threads, instead it's concurrent counterpart PriorityBlockingQueue is thread-safe as well as should hold upwards used inwards multithreaded environment. Priority queue provides O(log(n)) fourth dimension functioning for mutual enqueing as well as dequeing methods e.g. offer(), poll() as well as add(), but constant fourth dimension for retrieval methods e.g. peek() as well as element().
How to utilisation PriorityQueue inwards Java
Comparator provided to PriorityQueue. In this example, nosotros lead hold kept reveal of Items inwards PriorityQueue, whose natural ordering is decided past times it's price.
You tin lead hold a hold off at Item bird compareTo method, it's consistent with equals method and besides sorts Items based upon in that place price. I lead hold besides exercise Item every bit nested static bird here. By storing Item inwards priority queue, you lot tin e'er retrieve Item amongst lowest cost past times using poll() method of Queue interface.
You tin lead hold a hold off at Item bird compareTo method, it's consistent with equals method and besides sorts Items based upon in that place price. I lead hold besides exercise Item every bit nested static bird here. By storing Item inwards priority queue, you lot tin e'er retrieve Item amongst lowest cost past times using poll() method of Queue interface.
package test;
import java.util.PriorityQueue;
import java.util.Queue;
/**
* Java Program to demo How to utilisation PriorityQueue inwards Java. This instance besides demonstrate
* that PriorityQueue doesn't allow zilch elements as well as how PriorityQueue keeps elements i.e. ordering.
*
* @author
*/
public class PriorityQueueTest {
public static void main(String args[]) {
Queue<Item> items = new PriorityQueue<Item>();
items.add(new Item("IPone", 900));
items.add(new Item("IPad", 1200));
items.add(new Item("Xbox", 300));
items.add(new Item("Watch", 200));
System.out.println("Order of items inwards PriorityQueue");
System.out.println(items);
System.out.println("Element consumed from caput of the PriorityQueue : " + items.poll());
System.out.println(items);
System.out.println("Element consumed from caput of the PriorityQueue : " + items.poll());
System.out.println(items);
System.out.println("Element consumed from caput of the PriorityQueue : " + items.poll());
System.out.println(items);
//items.add(null); // zilch elements non allowed inwards PriorityQueue - NullPointerException
}
private static class Item implements Comparable<Item> {
private String name;
private int price;
public Item(String name, int price) {
this.name = name;
this.price = price;
}
public String getName() {
return name;
}
public int getPrice() {
return price;
}
@Override
public boolean equals(Object obj) {
if (obj == null) {
return false;
}
if (getClass() != obj.getClass()) {
return false;
}
final Item other = (Item) obj;
if ((this.name == null) ? (other.name != null) : !this.name.equals(other.name)) {
return false;
}
if (this.price != other.price) {
return false;
}
return true;
}
@Override
public int hashCode() {
int hash = 5;
hash = 97 hash + (this.name != null ? this.name.hashCode() : 0);
hash = 97 hash + this.price;
return hash;
}
@Override
public int compareTo(Item i) {
if (this.price == i.price) {
return this.name.compareTo(i.name);
}
return this.price - i.price;
}
@Override
public String toString() {
return String.format("%s: $%d", name, price);
}
}
}
Output:
Order of items inwards PriorityQueue
[Watch: $200, Xbox: $300, IPone: $900, IPad: $1200]
Element consumed from caput of the PriorityQueue : Watch: $200
[Xbox: $300, IPad: $1200, IPone: $900]
Element consumed from caput of the PriorityQueue : Xbox: $300
[IPone: $900, IPad: $1200]
Element consumed from caput of the PriorityQueue : IPone: $900
[IPad: $1200]
From the inwards a higher house output, it's clear that PriorityQueue keeps to the lowest degree value chemical constituent at head, where ordering is determined using compareTo() method. It doesn't proceed all elements inwards that guild though, alone caput beingness to the lowest degree value chemical constituent is guaranteed. This is inwards fact primary departure betwixt TreeSet as well as PriorityQueue inwards Java, erstwhile keeps all elements inwards a item sorted order, spell priority queue only keeps caput inwards sorted order. Another of import betoken to banking enterprise complaint is that PriorityQueue doesn't permit zilch elements as well as trying to add together zilch elements volition result inwards NullPointerException, as shown below :
Exception inwards thread "main" java.lang.NullPointerException
at java.util.PriorityQueue.offer(PriorityQueue.java:265)
at java.util.PriorityQueue.add(PriorityQueue.java:251)
at test.PriorityQueueTest.main(PriorityQueueTest.java:36)
Java Result: 1
Summary
Like whatever other Collection class, it's worth noting to cry upwards key points nearly PriorityQueue inwards Java.
1) PriorityQueue is non synchronized, if thread-safety is requirement utilisation BlockingPriorityQueue.
2) Queue retrieval methods similar poll(), peek() as well as element() access caput of Queue, which keeps to the lowest degree chemical constituent according to specified ordering.
3) Iterator returned past times PriorityQueue doesn't offering whatever ordering traversal guarantee.
4) PriorityQueue doesn't allow null elements, if you lot endeavour to add together null, it volition throw java.lang.NullPointerException.
That's all on what is PriorityQueue inwards Java as well as How to utilisation them. It's an exceptional class, which tin hold upwards used inwards exceptional scenarios, where you lot involve to swallow Orders inwards a item order, cry upwards BlockingQueue maintains insertion order, but if desire to maintain a custom order, PriorityQueue or BlockingPriorityQueue is correct collection to use. TreeSet besides provides similar functionality, but doesn't lead hold 1 curt retrieval cum removal method e.g. poll().
Further Learning
Java In-Depth: Become a Complete Java Engineer
Java Fundamentals: Collections
Data Structures as well as Algorithms: Deep Dive Using Java
Recommended Book
Though PriorityQueue has quite specialized use, it is 1 of the Collection class, which is frequently overlooked. Like whatever other Collection topic, Java Generics as well as Collection contains to a greater extent than or less of the best available information nearly PriorityQueue. If you lot similar to larn more, lead hold a re-create of that book.