PriorityQueue in Java

PriorityQueue is one of the queue implementation based on Heap. A (normal) queue follows first-in, first-out (FIFO) principle. So, the element waiting longest goes out next. But, PriorityQueue is a queue with priority and hence the element with highest need (or priority) goes next. It partially orders elements in the data structure which is weaker than sorted order.

I have discussed the heap data structure in a separate post (here). As discussed in the post; the elements can be ordered as per min-heap property or max-heap property. Elements can be ordered according to natural ordering or by the Comparator provided at the time of construction of the queue. Let's take a look at the simplest possible example. (Taken numbers from the heap post)

 import java.util.PriorityQueue;  
   
 public class PQDemo {  
      private static PriorityQueue<Integer> pq;  
   
      public static void main(String[] args) {  
           pq = new PriorityQueue<>(); //can pass Comparator in the argument 
           pq.offer(10);  
           pq.offer(45);  
           pq.offer(75);  
           pq.offer(70);  
           pq.offer(55);  
           pq.offer(90);  
           pq.offer(1001);  
   
           System.out.println(" Elements in the Priority Queue :" + pq.toString());  
             
           System.out.print(" Taking out elements from Priority Queue :");  
           while (!pq.isEmpty())  
                System.out.print(pq.poll() + ", ");  
      }  
 }  

Output:
Elements in the Priority Queue :[10, 45, 75, 70, 55, 90, 1001]
Taking out elements from Priority Queue :10, 45, 55, 70, 75, 90, 1001, 

Important Points from above program

• Normal iterator ( .toString()) doesn't print elements in sorted order. You need to use sort() method of Array class to sort it. (i.e. Arrays.sort(pq.toArray())
• poll() method removes elements from the queue in sorted order
• It is using default ordering technique (as provided in Integer class) and hence elements are stored in ascending order (Min-heap).
• No matter how many elements you put in above queue; the head will always have the smallest element.
• To use max-heap property; pq = new PriorityQueue<>(Collections.reverseOrder()); Check this post for details

 

API specification

[PriorityQueue<E> Java Doc - here]

Let's look at the specific details of the API:

1. It is an unbounded queue implementation and the default initial capacity is 11
2. offer() or add() inserts the specified element in the queue
3. poll() retrieves and removes the head of the queue, or returns null if the queue is empty
4. peek() retrieves the head of the queue but doesn't remove it. Returns null if queue is empty.
5. element() is similar to peek() with only exception that it throws exception if queue is empty.
6. remove() is similar to poll() with only exception that it throws exception if queue is empty.
7. size() returns number of elements in the queue.
8. This is not a thread safe API. So multiple threads should not access it concurrently.
9. Doesn't allow null elements. Putting null throws NullPointerException. 

that is it for now!!! keep posting your inputs.