Java Priority Queue (PriorityQueue) Example

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. For example, let’s say we have an application that generates stocks reports for daily trading session and it 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.

PriorityQueue class was introduced in Java 1.5 and 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 or we can provide a Comparator for ordering at the time of instantiation of queue.

PriorityQueue doesn’t allow null values and we can’t create PriorityQueue of Objects that are non-comparable, for example any custom classes we have. We use java Comparable and Comparator interfaces for sorting Objects and PriorityQueue 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.

PriorityQueue 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 multi-threading environment.

PriorityQueue implementation provides O(log(n)) time for enqueing and dequeing method. Let’s see an example of 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.

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 PriorityQueue.

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 test program, I get 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)

 

Reference: Java Priority Queue (PriorityQueue) Example from our JCG partner Pankaj Kumar at the Developer Recipes blog.

Do you want to know how to develop your skillset to become a Java Rockstar?

Subscribe to our newsletter to start Rocking right now!

To get you started we give you two of our best selling eBooks for FREE!

JPA Mini Book

Learn how to leverage the power of JPA in order to create robust and flexible Java applications. With this Mini Book, you will get introduced to JPA and smoothly transition to more advanced concepts.

JVM Troubleshooting Guide

The Java virtual machine is really the foundation of any Java EE platform. Learn how to master it with this advanced guide!

Given email address is already subscribed, thank you!
Oops. Something went wrong. Please try again later.
Please provide a valid email address.
Thank you, your sign-up request was successful! Please check your e-mail inbox.
Please complete the CAPTCHA.
Please fill in the required fields.

Leave a Reply


7 + three =



Java Code Geeks and all content copyright © 2010-2014, Exelixis Media Ltd | Terms of Use | Privacy Policy | Contact
All trademarks and registered trademarks appearing on Java Code Geeks are the property of their respective owners.
Java is a trademark or registered trademark of Oracle Corporation in the United States and other countries.
Java Code Geeks is not connected to Oracle Corporation and is not sponsored by Oracle Corporation.
Do you want to know how to develop your skillset and become a ...
Java Rockstar?

Subscribe to our newsletter to start Rocking right now!

To get you started we give you two of our best selling eBooks for FREE!

Get ready to Rock!
You can download the complementary eBooks using the links below:
Close