Java Priority Queue (PriorityQueue) Example

Filed Under: Java

Welcome to Priority Queue in Java tutorial. We know that Queue follows First-In-First-Out model but sometimes we need to process the objects in the queue based on the priority. That is when Java PriorityQueue is used.

For example, let’s say we have an application that generates stocks reports for daily trading session. This application processes a lot of data and takes time to process it. So customers are sending request to the application that is actually getting queued but we want to process premium customers first and standard customers after them. So in this case PriorityQueue implementation in java can be really helpful.

Java Priority Queue

priority queue java, PriorityQueue, java priority queue, java priority queue example

PriorityQueue class was introduced in Java 1.5 and it’s part of Java Collections Framework.

PriorityQueue is an unbounded queue based on a priority heap and the elements of the priority queue are ordered by default in natural order. We can provide a Comparator for ordering at the time of instantiation of priority queue.

Java Priority Queue doesn’t allow null values and we can’t create PriorityQueue of Objects that are non-comparable. We use java Comparable and Comparator for sorting Objects and Priority Queue use them for priority processing of it’s elements.

The head of the priority queue is the least element based on the natural ordering or comparator based ordering, if there are multiple objects with same ordering, then it can poll any one of them randomly. When we poll the queue, it returns the head object from the queue.

Java Priority Queue size is unbounded but we can specify the initial capacity at the time of it’s creation. When we add elements to the priority queue, it’s capacity grows automatically.

PriorityQueue is not thread safe, so java provides PriorityBlockingQueue class that implements the BlockingQueue interface to use in java multithreading environment.

Java Priority Queue implementation provides O(log(n)) time for enqueing and dequeing method.

Let’s see an example of java PriorityQueue for natural ordering as well as with Comparator.

We have our custom class Customer that doesn’t provide any type of ordering, so when we will try to use it with PriorityQueue we should provide a comparator object for that.

Customer.java


package com.journaldev.collections;

public class Customer {
	
	private int id;
	private String name;
	
	public Customer(int i, String n){
		this.id=i;
		this.name=n;
	}

	public int getId() {
		return id;
	}

	public String getName() {
		return name;
	}
	
}

We will use java random number generation to generate random customer objects. For natural ordering, I will use Integer that is also a java wrapper class.

Here is our final test code that shows how to use priority queue in java.

PriorityQueueExample.java


package com.journaldev.collections;

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Random;

public class PriorityQueueExample {

	public static void main(String[] args) {
		
		//natural ordering example of priority queue
		Queue<Integer> integerPriorityQueue = new PriorityQueue<>(7);
		Random rand = new Random();
		for(int i=0;i<7;i++){
			integerPriorityQueue.add(new Integer(rand.nextInt(100)));
		}
		for(int i=0;i<7;i++){
			Integer in = integerPriorityQueue.poll();
			System.out.println("Processing Integer:"+in);
		}
		
		//PriorityQueue example with Comparator
		Queue<Customer> customerPriorityQueue = new PriorityQueue<>(7, idComparator);
		addDataToQueue(customerPriorityQueue);
		
		pollDataFromQueue(customerPriorityQueue);
		
	}
	
	//Comparator anonymous class implementation
	public static Comparator<Customer> idComparator = new Comparator<Customer>(){
		
		@Override
		public int compare(Customer c1, Customer c2) {
            return (int) (c1.getId() - c2.getId());
        }
	};

	//utility method to add random data to Queue
	private static void addDataToQueue(Queue<Customer> customerPriorityQueue) {
		Random rand = new Random();
		for(int i=0; i<7; i++){
			int id = rand.nextInt(100);
			customerPriorityQueue.add(new Customer(id, "Pankaj "+id));
		}
	}
	
	//utility method to poll data from queue
	private static void pollDataFromQueue(Queue<Customer> customerPriorityQueue) {
		while(true){
			Customer cust = customerPriorityQueue.poll();
			if(cust == null) break;
			System.out.println("Processing Customer with ID="+cust.getId());
		}
	}

}

Notice that I am using java anonymous class for implementing Comparator interface and creating our id based comparator.

When I run above java priority queue example test program, it generates following output.


Processing Integer:9
Processing Integer:16
Processing Integer:18
Processing Integer:25
Processing Integer:33
Processing Integer:75
Processing Integer:77
Processing Customer with ID=6
Processing Customer with ID=20
Processing Customer with ID=24
Processing Customer with ID=28
Processing Customer with ID=29
Processing Customer with ID=82
Processing Customer with ID=96

From output it’s clear that least element was at head and got polled first. If we won’t provide comparator while creating customerPriorityQueue, it will throw ClassCastException at runtime.


Exception in thread "main" java.lang.ClassCastException: com.journaldev.collections.Customer cannot be cast to java.lang.Comparable
	at java.util.PriorityQueue.siftUpComparable(PriorityQueue.java:633)
	at java.util.PriorityQueue.siftUp(PriorityQueue.java:629)
	at java.util.PriorityQueue.offer(PriorityQueue.java:329)
	at java.util.PriorityQueue.add(PriorityQueue.java:306)
	at com.journaldev.collections.PriorityQueueExample.addDataToQueue(PriorityQueueExample.java:45)
	at com.journaldev.collections.PriorityQueueExample.main(PriorityQueueExample.java:25)

That’s all for java priority queue example, if you liked this article, please share and comment.

Comments

  1. Parag Sanjay Bhingre says:

    If we won’t provide comparator while creating customerPriorityQueue, it will throw ClassCastException at runtime.

    What do you mean by above statement?
    could you please explain with the example.

  2. Rajesh says:

    Really nice. Easy to understand.

  3. Nikunj Kapupara says:

    That article so clear to understand about the Priority Queue.

  4. Mustafa Olkun says:

    Thank you.
    It is clear article.

  5. sallapr says:

    Thanks, It helped.

  6. sriharsha says:

    So this is kind of Min/Max Heap ?

    1. theprimo says:

      It’s a Min heap. We can change the comparator logic slightly to make it Max heap.
      return – (int) (c1.getId() – c2.getId());

  7. Rat says:

    Good explanation. I thought by default PQ will store elements in inc order and when you poll, the highest priority element is least element and comparator is not required. Am I correct in my understanding?

  8. Shravya says:

    How can we test this example? I have written a class which uses the PriorityQueue class and comparator.
    Do I need to write test cases for them? if yes, how?

  9. Pramod says:

    Very nice article…Thanks

  10. Aidan says:

    Thank you! I am studying Game Artificial Intelligence, and can use this to optimize an A* pathfinder. Very cool and very nicely written code. Much Thanks!!!

  11. anitha says:

    How is priority queue different from other data structures, it gives a sorted list? We have other data structures that do that? How is different from others, when to use what?

    1. Himansu Nayak says:

      Hi Anitha,

      PriorityQueue is similar to a Sorted Queue.

    2. techb says:

      Priority queue is internally implemented as a binary minHeap.
      http://pages.cs.wisc.edu/~vernon/cs367/notes/11.PRIORITY-Q.html

  12. java2novice says:

    very nice. for more java examples, visit java2novice site.

Leave a Reply

Your email address will not be published. Required fields are marked *

close
Generic selectors
Exact matches only
Search in title
Search in content
Search in posts
Search in pages