PriorityQueue in Java 8

Previous
Next

In this post, we will see about Java 8 PriorityQueue.

When the objects are supposed to be processed on the basis of their priority, in that scenario we use PriorityQueue.

It’s a special type of queue (also, unbound queues) where the elements can be ordered either as per their natural ordering or based on a custom comparator implemented at the time of declaration.


Let’s understand the concept of Priority Queue with a daily life example,

Suppose two-person went to two different banks to deposit some money, Person A is serviced on the basis of the queue formed on the cash counter, Person B is serviced according to the token numbers provided by the bank (Underlying Queue), now here both follows FIFO (First in First Out) model, but their priorities are determined by different factors, for Person A it’s their arrival time (standing in a queue), but for Person B it’s just the token number (smaller number serviced first). Now, even here we can modify our system, that senior citizens are serviced first, so this is kind of a system where we have set few priorities (maybe on the basis of age).

Priority Queue Data Structure

Let’s say you want to read few books and prioritize it based on number of pages. You would like to read thinner books first and gradually move to thicker books.

In the given example, the front of the priority queue contains the smallest element, as per the specified ordering, and the rear contains the greatest element. Since the element is removed from the front, therefore the least element is removed first.

Some Important Points

  • Non-comparable objects cannot be implemented using Priority Queue.
  • Null is not allowed, as we can’t compare it with any value.
  • The basic retrieval operations like, poll(), remove(), peek() access the element at the front or at the head of the queue.

Constructors

  1. PriorityQueue(): Creating a Priority Queue with default initial capacity and following the natural ordering for its elements.
  2. PriorityQueue(Collection<E> c): It creates Priority Queue containing elements in the collection specified in the argument.
  3. PriorityQueue(int initialCapacity): It is similar to the PriorityQueue() with the specified initial capacity.
  4. PriorityQueue(int initialCapacity, Comparator<E> comparator): It is similar to PriorityQueue(int initialCapacity), but the extra parameter specifies the order of its element, which should be according to the specified comparator.

Methods

  1. boolean add(element) : This method will insert the element into this priority queue.
  2. boolean remove(element) : This method will remove one occurrence of element from the queue.
  3. poll() : This method returns the element at the head of the queue and hence removes it from the queue, else returns NULL (if the given queue is empty).
  4. peek() : This method is same as poll(), the only difference is, it does not remove the head after returning it.
  5. boolean contains(element) : It returns true if the given queue contains the specified element in it.
  6. clear() :This method will remove all the elements from a Priority Queue, that is it will empty an existing Priority Queue and does not delete it.
  7. boolean offer(element) : This method acts as add() method, as it is also used to insert a particular element into the Priority Queue.
  8. int size() : This method will return the number of elements in the priority queue.
  9. toArray() : This method return type is array, it returns all the elements of the priority queue in an array.
  10. Comparator comparator() : This method will return the comparator which is used to order the elements of the priority queue, and returns NULL value if the queue follows natural ordering.

Creating a PriorityQueue

Now, since we have discussed all the basic operations, methods and constructors of the Priority Queue Class, let’s see how to implement them in different ways,

Since, for integer type it is easy to differentiate, let’s implement for string type.

We will see how priorities will change the sequence for some of the best-selling books

Using No-arg constructor (Natural ordering)

In this program, we created a PriorityQueue of string type with no comparator, so it will use the natural ordering, which would according to the Dictionary (Alphabetically), added few string values to understand the working.
We can also see the application of add() and remove() here.

Code :

Output:

A Tale of Two Cities
And Then There Were None
Don Quixote
Dream of the Red Chamber
The Hobbit
The Master and Margarita

Using Custom Comparator

In this program, we have implemented the PriorityQueue with a custom comparator specified separately using its proper syntax, here we can see how we have prioritized according to the number of books.

Code :

Here, is the output for the code, where it is clearly seen that the elements are according to the number of pages of the book.

Output :

Book name is : The Master and Margarita and number of pages are :444
Book name is : Think and Grow Rich and number of pages are :401
Book name is : Dream of the Red Chamber and number of pages are :378
Book name is : And Then There Were None and number of pages are :342
Book name is : A Tale of Two Cities and number of pages are :322
Book name is : The Hobbit and number of pages are :276
Book name is : Don Quixote and number of pages are :246

That’s all about Priority Queue in java 8.

Previous
Next

Add Comment