PriorityQueue Example in Java

What is PriorityQueue

PriorityQueue is a Queue data structure that is available from Java 5. The queue is a FIFO (First In First Out) data structure. In a Queue normally the item we put first will be the one to get out first. So in a Queue, the order in which we add elements to the Queue determines the order in which the elements will come out from the queue(deque). Priority Queue is different in that expect. In PriorityQueue the elements are stored and are ordered by the priority of the elements. Elements with the highest priority are placed at the front of the Queue. When we take out items from the Queue(deque) element from the front of the queue is taken out first, which is an element with the highest priority is taken out first. So In PriorityQueue which item will come out first (deque) does not depend on the order in which elements were added, rather it depends on the priority of the elements. Then how do we assign priority to the elements? It is simple by default the ordering used by PriorityQueu is the natural ordering of the elements (from the front of the queue to back). Meaning smallest item based on the natural ordering is assigned the highest priority. We can also change this behavior by providing a Comparator that is used to order the elements.

java.util.PriorityQueue

In Java java.util.PriorityQueue is the implementation Class. It is an unbounded data structure which can grow as we add more data to it. Internally it uses array to hold the elements. It 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. The default capacity is 11. PriorityQueue is implemented as Min-Heap, that is element with minimum value is placed at the root of the Heap (front of the queue).

Class Diagram

Following Class diagram depicts Priority Queue in Java.

Constructors

PriorityQueue provides following constructors.
  • PriorityQueue(): Creates a PriorityQueue with the default initial capacity (11) that orders its elements according to their natural ordering of the elements.
  • PriorityQueue(int initialCapacity): Creates a PriorityQueue with the specified initial capacity that orders its elements according to their natural ordering.
  • PriorityQueue(int initialCapacity, Comparator comparator): Creates a PriorityQueue with the specified initial capacity that orders its elements according to the specified comparator.
  • PriorityQueue(PriorityQueue c): Creates a PriorityQueue containing the elements in the specified priority queue.
  • PriorityQueue(SortedSet c): Creates a PriorityQueue containing the elements in the specified sorted set.

Important methods

Following are the important methods that are inherited from Queue
  • peek:Retrieves, but does not remove, the front most element of the queue
  • poll: Retrieves and removes the front most element of the queue.
  • offer: add item to the front of the queue.
  • add: add item to the front of the queue, throws exception if element cannot be added.
  • remove: remove the front most item from the queue. It throws exception if queue is empty.

Examples

Example 1
Following example creates a priority queue with no argument constructor. Adds 3 items to it. Since we are not passing any Comparator, the items will be sorted based on the natural order. 1 will be at the front of the queue, followed by 2 and 3.
.
 Rear    6, 5, 1   Front 

Call peek and pop to see the items it returns. Notice that after calling poll() and then subsequently calling peek() it is returning a different item. As by calling poll() we have already removed the original element from the head of the queue.
//Create a PriorityQueue
Queue pq = new PriorityQueue<>();

//add item to the queue
pq.offer(1);
pq.offer(6);
pq.offer(5);
 
//print the content of the queue
System.out.println("\n Print Priority Queue");
pq.forEach(a->System.out.print(a + ", ")); 1, 6, 5, 
 
System.out.println("\n Peek the head of the queue: " + pq.peek());//1
System.out.println("\n Poll the head of the queue: " + pq.poll());//1
System.out.println("\n Peek the head of the queue: " + pq.peek());//5
Example 2
In this example we create a Priority Queue by supplying the capacity and Comparator Collections.reverseOrder(). This will make the Priority Queue to sort the elements in reverse order. So Highest element is at the front of the queue. This makes the Priority Queue like a Max Heap.
PriorityQueue pq2 = new PriorityQueue(15, Collections.reverseOrder());
pq2.add(1);
pq2.add(6);
pq2.add(5);
System.out.println("Print Priority Queue");
pq2.forEach(a->System.out.print(a + ",") ); 1, 6, 5, 

//print the content of the queue
System.out.println("\nPrint Priority Queue By poll");

System.out.println("\n Peek the head of the queue: " + pq2.peek());//6
System.out.println("\n Poll the head of the queue: " + pq2.poll());//6
System.out.println("\n Peek the head of the queue: " + pq2.peek());//5

Printing content of Queue

Example 3
In this example we see how we can print the content of the Queue.
//Create Queue
PriorityQueue pq1 = new PriorityQueue<>();
//Add 3 items
pq1.add(1);
pq1.add(6);
pq1.add(5);

System.out.println("Print Queue");
pq1.forEach(a->System.out.print(a + ", "));

System.out.println("Print Using Stream");
pq1.stream().forEach(a->System.out.print(a + ", "));

System.out.println("Print Using Iterator");
Iterator it = pq1.iterator();
while(it.hasNext()) {
  System.out.print(it.next() + ", ");
}
Order While Iterating
Order in which the elements will be accessed in the Priority Queue is not guaranteed while iterating it or accessing it though forEach method. Only when we use the method peek() or poll() methods guarantees that the item will be accessed from the front of the queue.
Key Points
  • Priority Queue is not synchronized.
  • O(log(n)) time for the enqueuing and dequeuing methods.
  • Linear time for the remove( ) and contains( ) methods.
  • Constant time for the peek( ) and size( ) methods.
  • We can specify the Comparator to manage the ordering of the data in the PriorityQueue.
  • PriorityQueue cannot contain null value.
  • While using Iterator or forEach loop does not guarantee any specific order.

References

No comments :

Post a Comment

Please leave your message queries or suggetions.