Java Priority Queue Example (PriorityQueue)

The elements of the priority queue are ordered according to their natural ordering, or by a Comparator provided at the time of queue creation. A priority queue does not permit null elements. Priority queue relying on natural ordering also does not permit insertion of non-comparable objects (doing so may result in ClassCastException).

Default capacity of PriorityQueue is 11. The Iterator provided in method iterator() is not guaranteed to traverse the elements of the priority queue in any particular order. Furthermore if you need ordered traversal, consider using Arrays.sort(pq.toArray()). Also PriorityQueue is not synchronized and should not be used in multi-threaded scenario where threads access it concurrently. Hence instead use the thread-safe java.util.concurrent.PriorityBlockingQueue class.

Constructors of PriorityQueue class

  • PriorityQueue():  Creates a PriorityQueue with the default initial capacity (11) that orders its elements according to their natural ordering.
  • PriorityQueue(Collection c):  Creates a PriorityQueue containing the elements in the specified collection.
  • 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(Comparator comparator):   Creates a PriorityQueue with the default initial capacity and whose elements are ordered 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.

Methods under Queue

  • add() –  This method is used to add elements at the end of Queue.
  • peek() –  This method is used to view the head of the element of queue without removing from queue. It returns null if the queue is empty.
  • element() –  This method is similar to peek(). This method throws NoSuchElementException if the queue is empty.
  • remove() –  This method removes and returns head element of the queue. Also  throws NoSuchElementException if the queue is empty.
  • poll() –  It removes and returns head element of the queue. It returns null if the queue id empty.

As shown in above picture Natural ordering of PriorityQueue allows its elements to be removed in sorted ascending order as per compareTo() method. So, while removing element in the PriorityQueue, the least element according to the specified ordering is removed first. If PriorityQueue is of type String then based on alphabetical order.

PriorityQueue Usage:

Let’s create a Priority Queue of integers and after adding the integers, we’ll remove them one by one from the priority queue and see how the smallest integer is removed first followed by the next smallest integer and so on.

#Output:

Priority Queue of user defined objects

In this example, we will see how to create a priority queue of user defined objects/class.

As we have see above as priority queue needs to compare its elements and order them accordingly, the user defined class must implement the Comparable interface default sorting behavior, or you must provide a Comparator while creating the priority queue. We will try to understand it by creating a Priority Queue of Employee class.

Using Comparable Interface:

The Employee class implements the Comparable interface and compares two employees by their salary.

Employee.Java

PriorityQueueExample.java

#Output:

As you can see in above result elements under PriorityQueue is in ascending order while we try to access/remove elements from it.

Using Comparator Interface:

We will see Priority Queue implementation for Employee class using comparator interface. Comparator interface provides multiple sorting sequences.

Employee.Java

MySalaryComparator.java

PriorityQueueExample.java

#Output:

Summary:

Below are key points regarding Priority Queue worth noting.

  1. PriorityQueue doesn’t allow null elements, if you try to add null, it will throw java.lang.NullPointerException.
  2. Iterator returned by PriorityQueue doesn’t guarantee any ordering while traversal its elements.
  3. PriorityQueue is not synchronized, if thread-safety is requirement use java.util.concurrent.PriorityBlockingQueue.

Happy Leaning. See you next time !

Sushil Singh

My name is Sushil Kumar Singh. I’m the founder, designer and editor of this blog. I would love to hear your thoughts and opinions on my articles. You can write to me at sushilsingh@learningsolo.com. I’ll try to respond as soon as possible. Alternatively, you can connect with me directly on linkedin or github or Facebook.

Leave a Reply

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.

  Subscribe  
Notify of