PriorityQueue is an unbounded Queue
implementation in Java, which is based on priority heap. PriorityQueue allows you
to keep elements in a particular order,
according to there natural order or custom order defined by Comparator interface in Java.
Head of priority queue data structure will always contain least element
with respect to specified ordering. For example, in this post, we will create a
PriorityQueue of Items, which are ordered based
upon there price, this will allow us
to process Items, starting from lowest price. Priority queue is also
very useful in implementing Dijkstra algorithm in Java. You can use to PriorityQueue to keep
unsettled nodes for processing. One of the key thing to remember about PriorityQueue in Java is
that it's Iterator doesn't guarantee any
order, if you want to traverse in ordered fashion, better use Arrays.sort(pq.toArray()) method. PriorityQueue is also
not synchronized, which means can
not be shared safely between multiple threads, instead it's concurrent
counterpart PriorityBlockingQueue is thread-safe and should
be used in multithreaded environment. Priority queue provides O(log(n)) time
performance for common enqueing and dequeing methods e.g. offer(), poll() and add(), but
constant time for retrieval methods e.g. peek() and element().
How to use PriorityQueue in Java
Here is one example of using PriorityQueue in Java,as I said earlier, you can use PriorityQueue to consume
elements in a particular order, which
can be natural ordering or any custom ordering defined by Comparator provided to PriorityQueue. In this
example, we have kept number of Items in PriorityQueue, whose
natural ordering is decided by it's price. You can take a look at Item class
compareTo method, it's consistent with equals method and also sorts
Items based upon there price. I have also create Item as nested static class
here. By storing Item in priority queue, you can always retrieve Item
with lowest price by using poll() method of Queue interface.
package test;
import java.util.PriorityQueue;
import java.util.Queue;
/**
* Java Program to show How to use
PriorityQueue in Java. This example also demonstrate
* that PriorityQueue doesn't allow null
elements and how PriorityQueue keeps elements i.e. ordering.
*
* @author
*/
public class PriorityQueueTest
{
public
static void
main(String args[]) {
Queue
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 in PriorityQueue");
System.out.println(items);
System.out.println("Element consumed from head of the PriorityQueue : "
+ items.poll());
System.out.println(items);
System.out.println("Element consumed from head of the PriorityQueue : "
+ items.poll());
System.out.println(items);
System.out.println("Element consumed from head of the PriorityQueue : "
+ items.poll());
System.out.println(items);
//items.add(null);
// null elements not allowed in PriorityQueue - NullPointerException
}
private
static class
Item implements
Comparable
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 in
PriorityQueue
[Watch:
$200, Xbox: $300, IPone: $900, IPad:
$1200]
Element consumed from head of
the PriorityQueue : Watch: $200
[Xbox:
$300, IPad: $1200, IPone: $900]
Element consumed from head of
the PriorityQueue : Xbox: $300
[IPone:
$900, IPad: $1200]
Element consumed from head of
the PriorityQueue : IPone: $900
[IPad:
$1200]
From the above output, it's clear that PriorityQueue keeps
least value element at head, where ordering is determined using compareTo() method. It doesn't
keep all elements in that order though, only head being least value element is
guaranteed. This is in fact main difference between TreeSet and PriorityQueue in Java,
former keeps all elements in a particular sorted order, while priority queue only keeps
head in sorted order. Another important point to note is that PriorityQueue doesn't permit null elements and trying to
add null elements will result in NullPointerException, as shown
below :
Exception in 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 any other Collection class, it's worth noting to remember key points
about PriorityQueue in Java.
2) Queue retrieval methods like poll(), peek() and element() access
head of Queue, which keeps least element according to
specified ordering.
3) Iterator returned by PriorityQueue doesn't
offer any ordering traversal guarantee.
4) PriorityQueue doesn't allow null elements, if
you try to add null, it will throw java.lang.NullPointerException.
That's all on what is PriorityQueue in Java and How to use them.
It's an special class, which can be used in special scenarios, where you need
to consume Orders in a particular order, remember BlockingQueue maintains
insertion order, but if want to maintain a custom order, PriorityQueue or BlockingPriorityQueue is right
collection to use. TreeSet also provides similar
functionality, but doesn't have one short retrieval cum removal method e.g. poll().
Recommended
Book
Though PriorityQueue has quite specialized use, it is one of the
Collection class, which is often overlooked. Like any other Collection topic, Java Generics and Collection
contains some of the best available information about PriorityQueue. If you
like to learn more, take a copy of that book.
Source:http://javarevisited.blogspot.com/2013/10/what-is-priorityqueue-data-structure-java-example-tutorial.html
Tidak ada komentar:
Posting Komentar