Wednesday, October 2, 2013

What is PriorityQueue or priority queue data structure in Java with Example - Tutorial

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

PriorityQueue Example in JavaHere 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<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 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<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 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.

1) PriorityQueue is not synchronized, if thread-safety is requirement use BlockingPriorityQueue.
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.

5 comments :

Anonymous said...

Is it priority queue or PriorityQueue? I think data structure is known as priority queue and the collection class in Java which implement it is named as PriorityQueue, correct me if I am wrong.

KRISHNAMOORTHY said...

Hi.,
Thanks for the nice explanation.I love ur blog

can u explain the below lines in detail
hash = 97 hash + (this.name != null ? this.name.hashCode() : 0);
hash = 97 hash + this.price;

the above lines are not executing and also would like to know more about that.

Thanks,
Krish


Anonymous said...

I see Priority Queue is only available from Java 1.5, is there a way to use this in Java 1.4 code? Any open source library which provides backport implementation of Java 1.5 and 1.6 Collection classes?

Anonymous said...

Hi KRISHNAMOORTHY
There's a missing * operator in the two lines you pasted

The corrected lines are:

hash = 97 * hash + (this.name != null ? this.name.hashCode() : 0);
hash = 97 * hash + this.price;

kebhari said...

Very nice analysis. It is a little disconcerting to observe that most businessmen have depended too much on the media because it is where the bulk of the people and the interactions are, but have also disregarded the real focus of their marketing, which is the consumer. I enjoyed reading this post. Thanks for the insights!

Post a Comment