Saturday, October 12, 2013

PriorityQueue in Java

In this post, we dig in the Queue interface and then into PriorityQueue implementation of the Queue interface with examples. Here we'll see the basic concept of priority queue and its methods in detail. 

Queue


In general, a queue is a line of people or things waiting to be handled, usually in sequential order starting at the beginning or top of the line or sequence. 


In computer technology, a queue is a sequence of work objects that are waiting to be processed.







Queue Interface
A Queue is designed to hold a list of "to-dos," or things to be processed in some way. Although other orders are possible, queues are typically thought of as FIFO (first-in,first-out).
Besides basic Collection operations, queues provide additional insertion, extraction, and inspection operations. Each of these methods exists in two forms: one throws an exception if the operation fails, the other returns a special value either null or false, depending on the operation.
Operation Throws exception Return special value
Insert add( e ) offer ( e )
Remove remove (e ) poll ( e )
Examine element (e ) peek ( e )

The offer method inserts an element if possible, otherwise returning false. This differs from the Collection.add method, which can fail to add an element only by throwing an unchecked exception. The offer method is designed for use when failure is a normal, rather than exceptional occurrence, for example, in fixed-capacity (or "bounded") queues\

The remove() and poll() methods differ only in their behavior when the queue is empty: the remove() method throws an exception, while the poll() method returns null.

The element() and peek() methods return, but do not remove, the head of the queue.

Queue implementations generally do not allow insertion of null elements, although some implementations, such as LinkedList, do not prohibit insertion of null

PriorityQueue 

An unbounded priority queue based on a priority heapThe purpose of a PriorityQueue is to create a "priority-in, priority out" queue as opposed to a typical FIFO queue.
A PriorityQueue's elements are ordered either by natural ordering (in which case the elements that are sorted first will be accessed first) or according to a Comparator. In either case, the elements' ordering represents their relative priority.
  • 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).
  • 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.



Note that this implementation is not synchronized. Multiple threads should not access a PriorityQueue instance concurrently if any of the threads modifies Note that this implementation is not synchronized. Multiple threads should not access a PriorityQueue instance concurrently if any of the threads modifies

Let's see an example of Priority Queue

Sample Output
head of queue: 2
2
3
5
6
8
9
64
poll : null
peek : null
2
3
5
6
8
9
64
Exception in thread "main" java.util.NoSuchElementException
 at java.util.AbstractQueue.remove(Unknown Source)
 at PriorityQueueDemo.main(PriorityQueueDemo.java:22)
I hope, now it clear how to use priority queue and it's methods.


Let's see an another example of priority queue with Comparator with out own ordering instead of natural ordering

Sample Output
head of queue: 64
64
9
8
6
5
3
2
Exception in thread "main" java.lang.NullPointerException
at java.util.PriorityQueue.offer(Unknown Source)
at PriorityQueueComparatorDemo.main(PriorityQueueComparatorDemo.java:17)

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()).

Let see this with the help of another example


Sample Output 
Natural order
2
3
5
6
8
9
64
Iterator:
2
3
6
8
5
9
64


Example of priority Queue sorting by String Length
Sample Output
olx
java
Myntra
flipkart

We'll see an example of how PriorityQueue use in real world example. The order of patients to be treated by a doctor can be determined by checking if it's a emergency case or not.








If you know anyone who has started learning Java, why not help them out! Just share this post with them. 
Thanks for studying today!...

1 comment:

  1. Thanks for sharing this article. This article is really very helpful.
    Java training

    ReplyDelete