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


Iterate over Java MAP

Map is an interface and is a part of the java collections framework. Java collections framework provides a number of Map implementations like HashMap, TreeMap, LinkedHashMap etc. This post contains different ways of traversing through a HashMap, which are given below:
Following section illustrates different ways to traverse the map data. Since map contains key-value data, most of them traverse through the keys and get the corresponding data.
Map initialization
Following code creates instance of a TreeMap and puts 5 key-value pairs to it.
Map map = new TreeMap();
map.put(1,"A");
map.put(3,"C");
map.put(2,"B");
map.put(4,"D");
map.put(5,"E");
Iterator
Traverse using Iterator of the key set.
System.out.println("Print using Iterator");
Iterator it = map.keySet().iterator();

while (it.hasNext()) {
  Integer k = it.next();
  String  v = map.get(k);
  System.out.print( "Key=" + k + " Value=" + v);
}
Forloop
Following code traverse the map by using a for loop on the key set.
//For loop over the keySet
System.out.println("\nPrint using for loop");
for (Integer k : map.keySet()) {
  String  v = map.get(k);
  System.out.print( "Key=" + k + " Value=" + v);
}
Stream
Following code traverse the map using a stream on the key set.
System.out.println("\nPrint using stream");
map.keySet().stream().forEach(key -> {System.out.print ("Key=" + key + " Value=" + map.get(key)); });
forEach
Following code traverse using forEach method. forEach method was introduced in java 8.
System.out.println("\nPrint using forEach");
map.forEach((k, v) ->System.out.print( "Key=" + k + " Value=" + v)) ;