PriorityQueue in Java explained with examples

Read Time:7 Minute, 41 Second

Table of Contents

In Java, a priority queue is a special form of the queue in which all components are ordered either by their natural ordering or by a custom Comparator provided at the time of construction. Before talking about priority queues, let’s look at what a regular queue is.

The first in, first out (FIFO) structure is used in a typical queue. If three messages – m1, m2, and m3 – enter the queue in that sequence, they will exit in the same order.

What is the purpose of queues?

Let’s imagine we have highly fast data generators (for example, when a user clicks on a web page). However, we intend to ingest this data more slowly later. In this scenario, the producer would send all of the messages to the queue, and a consumer would consume them at a slower rate later from the queue.

According to the given ordering, the front of the priority queue includes the least element, and the back of the priority queue has the greatest element.

According to the stated ordering, the least important element is removed first on removing an element from the priority queue. The Priority Queue class implements the Queue interface and is part of Java’s collections system. The Priority Queue class in Java has the following class structure.

SUGGESTED READ

The following are some key factors to remember about Priority Queue:

  • Null is not allowed in PriorityQueue.
  • We can’t establish a PriorityQueue of non-comparable objects.
  • Unbound queues are PriorityQueues.
  • The last entry in the specified ordering is at the head of this queue. If there are numerous components tied for the lowest value, the head is one of the – ties broken at random.
  • Because PriorityQueue isn’t thread-safe, Java provides a workaround.
  • In a Java multithreading environment, the PriorityBlockingQueue class implements the BlockingQueue interface.
  • The poll, delete, peek, and element procedures all access the element at the top of the queue.
  • The add and poll techniques take O(log(n)) time.
  • AbstractQueue, AbstractCollection, Collection, and Object all have methods that it inherits.

Putting Together a Priority Queue

Let’s construct an integer Priority Queue and add some integers to it. After adding the integers to the priority queue, we’ll remove them to notice how the smallest integer gets deleted first, then the next smallest integer, and so on.

Let’s look at the identical scenario using a String Priority Queue.

In this scenario, the smallest String gets deleted first, as per the natural ordering of Strings.

Using a custom Comparator to create a Priority Queue

Assume that we need to establish a priority queue of String items, with the shortest String being processed first. We may establish such a priority queue by passing a custom Comparator that compares two Strings by length. Here’s an illustration:

SUGGESTED READ

Take notice of how the shortest string gets deleted first.

User-defined object priority queue

Custom orders are also available, and we can accomplish so with the assistance of a comparator. Let’s start by making an integer priority queue. But this time, let’s sort the results by value in descending order. To accomplish this, we must first construct an integer comparator:

We implement the comparator interface and override the compare method to create a comparator. We may retrieve the result in descending order by using intOne< intTwo? 1: -1. The results would have been in increasing order if we had used intOne > intTwo? 1: -1. We need to add the comparator to the priority queue now that we’ve got it. This is how we can accomplish it:

The remaining code, which adds elements to the priority queue and prints them, is as follows:

We can observe that the comparator did a good job. The integers are now being delivered in descending order via the priority queue. In this example, you’ll learn how to create a priority queue of user-defined items.

SUGGESTED READ

Because a priority queue must compare and organize its contents, the user-specified class must implement the Comparable interface. Or a Comparator must be provided when the priority queue is created. If you add new objects to the priority queue, it will throw a ClassCastException.

Take a look at the example below, in which we establish a priority queue for a custom class called Employee. The Employee class uses the Comparable interface to compare the salaries of two employees.

Take note of how the code employee with the lowest wage is the first to be fired.

Java Objects in a priority queue

We’ve seen how to use strings and integers with priority queues up to this point. Priority queues containing custom Java objects are commonly used in real-world applications. Let’s start by making an EcommerceOrder class to hold customer order information:

It is a straightforward Java class for keeping track of customer orders. This class implements a similar interface, allowing us to choose how this item should be prioritized in the priority queue. The compareTo function in the above code determines the ordering. The line o.ordId > this.ordId ?1: -1 specifies that the orders should be sorted in the ordId field’s decreasing order.

SUGGESTED READ

The code that builds a priority queue for the EcommerceOrder object is as follows:

Three e-commerce orders have been made and added to the priority queue in the code above. We receive the following output when we run this code:

The result is in descending order of ordId, as intended.

Prioritizing based on the ordAmount parameter

This is yet another true story. Let’s say the ordId prioritizes the eCommerceClientOrder object by default. However, we’ll need the means to prioritize based on orderAmount. You might imagine that we can edit the eCommerceOrder class’s compareTo function to order based on ordAmount.

However, because the eCommerceOrder class is used in various locations throughout the application, changing the compareTo function directly would cause problems elsewhere. The answer is simple: we can construct a new custom comparator for the eCommerceOrder class and use it in conjunction with the priority queue. The code for the custom comparator is as follows:

SUGGESTED READ

It looks a lot like the custom integer comparator we saw before.

The line ordOne.getOrderAmount() < ordTwo.getOrderAmount()? 1: -1; shows that we must prioritize according to orderAmount in decreasing order. The code that constructs the priority queue is as follows:

In the preceding code, the comparator is passed to the priority queue in the next line:

After running this code, we get the following result:

We can see that the data is sorted by ordAmount in descending order.

SUGGESTED READ

Java’s Minimum Priority Queue

The least or smallest element is at the front of the queue in the natural ordering of the Priority Queue. As a result, the ordering is ascending. With ascending order of components, this is known as the “Min priority queue.” The Java program below demonstrates how the Min Priority Queue is implemented in Java.

Java’s Maximum Priority Queue

The elements in the min priority queue are in ascending order. In contrast, the elements in the max priority queue are in descending order, i.e. the head of the Max priority queue returns the greatest element in the queue. The code snippet below shows how to use the Java Max Priority Queue.

Example: Natural ordering priority queues

Here’s some code that demonstrates how to make a simple string priority queue.

Example: Priority Queues in Java

We added a few integers to the queue in any order in the example above. The components were then printed once I iterated over the queue. As you can see above, the items are not saved in sorted order. As previously stated, binary heap only guarantees semi-ordering: elements in upper nodes are more (or fewer) than those in lower nodes. For example, in a max-heap, parents are always greater than their children. Heaps, unlike Binary Search Trees, do not keep absolute left-to-right ordering.

Example: Priority Queue Comparator

Example: methods of PriorityQueue using a Java program

Conclusion

In this article, you learned what a priority queue is, how to utilize one, how to create one with a custom comparator, and how to include user-defined objects in a priority queue.

SUGGESTED READ

A PriorityQueue is a queue type that allows Java programmers to insert components in any order but retrieve them in a predefined (sorted) order. The priority queue’s elements are sorted using a Comparator provided when the queue was built.

PriorityQueue is a valuable built-in collection that should be familiar to all Java developers. You’ll have an additional tool in your toolkit to design efficient applications once you’ve learned it.

When learning about priority queues, it’s crucial to understand the fundamental ideas, which are quite simple and help you make informed design decisions.

Source: https://www.codeunderscored.com/priorityqueue-in-java/

WP Ad Inserter plugin for WordPress