Java Programming Techniques and APIs

Priority Queue In Java

Board Infinity
Board Infinity
Priority Queue In Java

    Understand Serialization and Deserialization in Java

    A quick guide to Stack Class in Java

    A Quick Guide to String Builder in Java

    Understanding Garbage Collection in Java

    What are Functional Interfaces in Java?

    How to Handle Exceptions in Java?

    A practical guide on Synchronization in Java

    A Guide to Association, Aggregation, and Composition in Java

    How to Read files in Java?

    A Quick Guide to Linked Hashmap in Java

    Understanding JDBC in JAVA

    What is Static Class in JAVA?

    How to Read a File in JAVA?

    Checked vs Unchecked Exceptions in Java

    Priority Queue In Java

    Java Server Page: Introduction

    Volatile Keyword in Java

    Java Array and ArrayList: Differences

    Regex in Java

    Packages in Java

    Thread Priority in Java: What is it & How to set?

    Java Bytecode

    Hashtable in Java

    Lambda Expression in Java

    Java Stream

    LinkedList in Java

    Sorting A Hashmap In Java

    Finally Block In Java

    Trim in Java

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

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