Priority Queue In Java | Board Infinity

Introduction

A priority queue is an abstract data-type similar to regular queue or stack data structure. Each element in a priority queue has an associated priority.

In a priority queue, elements with high priority are served before elements with low priority.

The heap data structure's functionality is provided by the PriorityQueue class.

It conforms to the Queue interface.

The Queue interface is implemented by the Java PriorityQueue class.

Priority queue elements are retrieved in sorted order, as opposed to conventional queue elements.

Assume we wish to get elements in ascending order. In this situation, the smallest element will be at the top of the priority queue. When this element is retrieved, the queue's head will be the next smallest element.

It is vital to realize that priority queue entries may not be sorted. Elements, on the other hand, are always returned in sorted order.

Making a PriorityQueue

Importing the java.util.PriorityQueue package is required to establish a priority queue. Here's how to make a priority queue in Java when we import the library.

PriorityQueue<Integer> numbers = new PriorityQueue<>();

We've constructed a priority queue without any arguments. In this situation, the smallest member of the priority queue is at the top of the queue. And elements are deleted from the queue in ascending order.

The Comparator interface, on the other hand, allows us to change the ordering of components.

PriorityQueue Declaration

Let's look at the declaration for java.util.PriorityQueue class.

public class PriorityQueue<E> extends AbstractQueue<E> implements Serializable

A few key points about Priority Queue are as follows:

PriorityQueue does not support null values.
We can't make a PriorityQueue of non-comparable objects.
Unbound queues are PriorityQueues.
The least element in this queue according to the provided ordering is at the top. If numerous elements are tied for the lowest value, the head is one of them – ties are broken at random.
Because PriorityQueue is not thread-safe, Java provides the PriorityBlockingQueue class, which implements the BlockingQueue interface and can be used in a multithreading context.
The queue retrieval operations poll, delete, peek, and element access the queue's first element.
It has O(log(n)) time for the add and poll techniques.
It inherits methods from the abstract classes AbstractQueue, AbstractCollection, Collection, and Object.

Examples

TestCollection12.java

import java.util.*;

class TestCollection12{

public static void main(String args[]){

PriorityQueue<String> queue=new PriorityQueue<String>();

queue.add("Amit");

queue.add("Vijay");

queue.add("Karan");

queue.add("Jai");

queue.add("Rahul");

System.out.println("head:"+queue.element());

System.out.println("head:"+queue.peek());

System.out.println("iterating the queue elements:");

Iterator itr=queue.iterator();

while(itr.hasNext()){

System.out.println(itr.next());

}

queue.remove();

queue.poll();

System.out.println("after removing two elements:");

Iterator<String> itr2=queue.iterator();

while(itr2.hasNext()){

System.out.println(itr2.next());

}

Output

head:Amit

Iterating the queue elements:

Amit

Jai

Karan

Vijay

Rahul

after removing two elements:

Karan

Vijay

Rahul

write your code here: Coding Playground

Java PriorityQueue: Book

Let's look at a PriorityQueue example in which we add books to the queue and print every book in the queue. PriorityQueue elements must be of Comparable type. Classes like String and Wrapper are by default Comparable. You must implement the Comparable interface in order to add user-defined objects to PriorityQueue.

LinkedListExample.java

import java.util.*;

class Book implements Comparable<Book>{

int id;

String name,author,publisher;

int quantity;

public Book(int id, String name, String author, String publisher, int quantity) {

this.id = id;

this.name = name;

this.author = author;

this.publisher = publisher;

this.quantity = quantity;

}

public int compareTo(Book b) {

if(id>b.id){

return 1;

}else if(id<b.id){

return -1;

}else{

return 0;

}

public class LinkedListExample {

public static void main(String[] args) {

Queue<Book> queue=new PriorityQueue<Book>();

//Creating Books

Book b1=new Book(121,"Let us C","Yashwant Kanetkar","BPB",8);

Book b2=new Book(233,"Operating System","Galvin","Wiley",6);

Book b3=new Book(101,"Data Communications & Networking","Forouzan","Mc Graw Hill",4);

//Adding Books to the queue

queue.add(b1);

queue.add(b2);

queue.add(b3);

System.out.println("Traversing the queue elements:");

//Traversing queue elements

for(Book b:queue){

System.out.println(b.id+" "+b.name+" "+b.author+" "+b.publisher+" "+b.quantity);

}

queue.remove();

System.out.println("After removing one book record:");

for(Book b:queue){

System.out.println(b.id+" "+b.name+" "+b.author+" "+b.publisher+" "+b.quantity);

}

Output:

Transversing the queue elements:

101 Data Communications and Networking Forouzan Mc Graw Hill 4

233 Operating System Galvin Wiley 6

121 Let us C Yashwant Kanetkar BPB 8

After removing one book record:

121 Let us C Yashwant Kanetkar BPB 8

233 Operating System Galvin Wiley 6

write your code here: Coding Playground

Applications

Dijkstra and Prim's algorithms are being implemented.
After K negations, maximize the array sum.

Conclusion

The Priority Queue is an important data structure when dealing with items with various priorities. The main benefit of employing a priority queue is that you can immediately access the highest priority item with a time complexity of only O. (1). The sole drawback to employing Priority Queues is that the enqueue and dequeue operations are sluggish and have an O(1) time complexity (log n).