Java Program to Implement PriorityQueue

«
»

PriorityQueue in Java is a class that implements a priority queue data structure. It stores elements in priority order, which means that the element with the highest priority is always at the front of the queue. It can be used to manage tasks, jobs or any other items that have a priority associated with them. PriorityQueue in Java provides several methods for adding, removing, and checking the elements in the queue.

Problem Description

Write a Java Program to implement Priority Queue.

Problem Solution

In a priority queue, an element with high priority is served before an element with low priority. If two elements have the same priority, they are served according to their order in the queue. Here priority queue is implemented using a max heap.

Declaration of PriorityQueue
The PriorityQueue class in Java provides an implementation of a priority queue using a heap data structure. You can create a priority queue using the following syntax:

PriorityQueue<DataType> pq = new PriorityQueue<>();

In this syntax, DataType represents the data type of the elements that the priority queue will hold. You can replace DataType with any valid Java data type, such as Integer, String, or a custom class.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
advertisement
advertisement

Operations on PriorityQueue in Java
Priority queues are useful in scenarios where you need to process elements in a specific order based on their priority. Here are some common methods that you can use:

  • Adding Elements: To add elements to the priority queue, you can use the add() method or the offer() method. These methods add elements to the queue while maintaining the order of the elements based on their priority.
  • Removing Elements: To retrieve and remove the element with the highest priority from the queue, you can use the poll() method. This method returns and removes the head of the queue (i.e., the element with the highest priority).
  • Accessing the Elements: To access elements from a priority queue, we can use the peek() method. It retrieves the elements, but does not remove, the head of the queue, or returns null if the queue is empty.
Program/Source Code

Here is the source code of the Java Program to implement Priority Queue. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

/**
 ** Java Program to implement PriorityQueue
 **/
 
import java.util.Scanner;
 
/** class Task **/
class Task
{
    String job;
    int priority;
 
    /** Constructor **/
    public Task(String job, int priority)
    {
        this.job = job;
        this.priority = priority; 
    }
    /** toString() **/
    public String toString() 
    {
        return "Job Name : "+ job +"\nPriority : "+ priority;
    }
}
 
/** Class PriorityQueue **/
class PriorityQueue
{
    private Task[] heap; 
    private int heapSize, capacity;
 
    /** Constructor **/
    public PriorityQueue(int capacity)
    {    
        this.capacity = capacity + 1;
        heap = new Task[this.capacity];
        heapSize = 0;
    }
    /** function to clear **/
    public void clear()
    {
        heap = new Task[capacity];
        heapSize = 0;
    }
    /** function to check if empty **/
    public boolean isEmpty()
    {
        return heapSize == 0;
    }
    /** function to check if full **/
    public boolean isFull()
    {
        return heapSize == capacity - 1;
    }
    /** function to get Size **/
    public int size()
    {
        return heapSize;
    }
    /** function to insert task **/
    public void insert(String job, int priority)
    {
        Task newJob = new Task(job, priority);
 
        heap[++heapSize] = newJob;
        int pos = heapSize;
        while (pos != 1 && newJob.priority > heap[pos/2].priority)
        {
            heap[pos] = heap[pos/2];
            pos /=2;
        }
        heap[pos] = newJob;    
    }
    /** function to remove task **/
    public Task remove()
    {
        int parent, child;
        Task item, temp;
        if (isEmpty() )
        {
            System.out.println("Heap is empty");
            return null;
        }
 
        item = heap[1];
        temp = heap[heapSize--];
 
        parent = 1;
        child = 2;
        while (child <= heapSize)
        {
            if (child < heapSize && heap[child].priority < heap[child + 1].priority)
                child++;
            if (temp.priority >= heap[child].priority)
                break;
 
            heap[parent] = heap[child];
            parent = child;
            child *= 2;
        }
        heap[parent] = temp;
 
        return item;
    }
}
 
/** Class PriorityQueueTest **/
public class PriorityQueueTest
{
    public static void main(String[] args)
    {
        Scanner scan = new Scanner(System.in);
        System.out.println("Priority Queue Test\n");   
 
        System.out.println("Enter size of priority queue ");
        PriorityQueue pq = new PriorityQueue(scan.nextInt() );
 
        char ch;
        /*  Perform Priority Queue operations */
        do    
        {
            System.out.println("\nPriority Queue Operations\n");
            System.out.println("1. insert");
            System.out.println("2. remove");
            System.out.println("3. check empty");
            System.out.println("4. check full");
            System.out.println("5. clear");
            System.out.println("6. size");
 
            int choice = scan.nextInt();            
            switch (choice) 
            {
            case 1 : 
                System.out.println("Enter job name and priority");
                pq.insert(scan.next(), scan.nextInt() );                     
                break;                          
            case 2 : 
                System.out.println("\nJob removed \n\n"+ pq.remove()); 
                break;        
            case 3 : 
                System.out.println("\nEmpty Status : "+ pq.isEmpty() );
                break; 
            case 4 : 
                System.out.println("\nFull Status : "+ pq.isFull() );
                break; 
            case 5 : 
                System.out.println("\nPriority Queue Cleared");
                pq.clear();
                break;    
            case 6 : 
                System.out.println("\nSize = "+ pq.size() );
                break;         
            default : 
                System.out.println("Wrong Entry \n ");
                break;   
            }    
 
            System.out.println("\nDo you want to continue (Type y or n) \n");
            ch = scan.next().charAt(0);                        
        } while (ch == 'Y'|| ch == 'y');            
    }
}
Program Explanation

1. The program creates a priority queue of tasks based on their importance.
2. The program defines a class called Task, which has two instance variables: job (a string representing the name of the task) and priority (an integer representing the priority of the task). The class also has a constructor that takes these two values as arguments, and a toString() method that returns a string representation of the task.
3. The program defines another class called PriorityQueue, which is the implementation of the priority queue. This class has two instance variables: heap (an array of Task objects) and heapSize (an integer representing the number of tasks currently in the queue).
4. It also has a constructor that takes the maximum size of the queue as an argument, and several methods to perform operations on the queue. These methods include

  • clear() – To remove all tasks from the queue.
  • isEmpty() – To check if the queue is empty.
  • isFull() – Tto check if the queue is full.
  • size() – To get the number of tasks in the queue.
  • insert() – To add a new task to the queue.
  • remove() – To remove and return the highest-priority task from the queue.

5. The program has another class called PriorityQueueTest that lets users interact with the list. Users can add or remove tasks, check if the list is empty or full, clear the list, and see the number of tasks in the list.
6. The program can tell users what happens after they choose an action. It also has a way to stop running when users choose to exit.

Program Output
Priority Queue Test
 
Enter size of priority queue
7
 
Priority Queue Operations
 
1. insert
2. remove
3. check empty
4. check full
5. clear
6. size
1
Enter job name and priority
job1 24
 
Do you want to continue (Type y or n)
 
y
 
Priority Queue Operations
 
1. insert
2. remove
3. check empty
4. check full
5. clear
6. size
1
Enter job name and priority
job2 6
 
Do you want to continue (Type y or n)
 
y
 
Priority Queue Operations
 
1. insert
2. remove
3. check empty
4. check full
5. clear
6. size
1
Enter job name and priority
job3 28
 
Do you want to continue (Type y or n)
 
y
 
Priority Queue Operations
 
1. insert
2. remove
3. check empty
4. check full
5. clear
6. size
1
Enter job name and priority
job4 63
 
Do you want to continue (Type y or n)
 
y
 
Priority Queue Operations
 
1. insert
2. remove
3. check empty
4. check full
5. clear
6. size
1
Enter job name and priority
job5 5
 
Do you want to continue (Type y or n)
 
y
 
Priority Queue Operations
 
1. insert
2. remove
3. check empty
4. check full
5. clear
6. size
1
Enter job name and priority
job6 94
 
Do you want to continue (Type y or n)
 
y
 
Priority Queue Operations
 
1. insert
2. remove
3. check empty
4. check full
5. clear
6. size
1
Enter job name and priority
job7 14
 
Do you want to continue (Type y or n)
 
y
 
Priority Queue Operations
 
1. insert
2. remove
3. check empty
4. check full
5. clear
6. size
6
 
Size = 7
 
Do you want to continue (Type y or n)
 
y
 
Priority Queue Operations
 
1. insert
2. remove
3. check empty
4. check full
5. clear
6. size
4
 
Full Status : true
 
Do you want to continue (Type y or n)
 
y
 
Priority Queue Operations
 
1. insert
2. remove
3. check empty
4. check full
5. clear
6. size
2
 
Job removed
 
Job Name : job6
Priority : 94
 
Do you want to continue (Type y or n)
 
y
 
Priority Queue Operations
 
1. insert
2. remove
3. check empty
4. check full
5. clear
6. size
2
 
Job removed
 
Job Name : job4
Priority : 63
 
Do you want to continue (Type y or n)
 
y
 
Priority Queue Operations
 
1. insert
2. remove
3. check empty
4. check full
5. clear
6. size
2
 
Job removed
 
Job Name : job3
Priority : 28
 
Do you want to continue (Type y or n)
 
y
 
Priority Queue Operations
 
1. insert
2. remove
3. check empty
4. check full
5. clear
6. size
2
 
Job removed
 
Job Name : job1
Priority : 24
 
Do you want to continue (Type y or n)
 
y
 
Priority Queue Operations
 
1. insert
2. remove
3. check empty
4. check full
5. clear
6. size
2
 
Job removed
 
Job Name : job7
Priority : 14
 
Do you want to continue (Type y or n)
 
y
 
Priority Queue Operations
 
1. insert
2. remove
3. check empty
4. check full
5. clear
6. size
2
 
Job removed
 
Job Name : job2
Priority : 6
 
Do you want to continue (Type y or n)
 
y
 
Priority Queue Operations
 
1. insert
2. remove
3. check empty
4. check full
5. clear
6. size
2
 
Job removed
 
Job Name : job5
Priority : 5
 
Do you want to continue (Type y or n)
 
y
 
Priority Queue Operations
 
1. insert
2. remove
3. check empty
4. check full
5. clear
6. size
2
Heap is empty
 
Job removed
 
null
 
Do you want to continue (Type y or n)
 
y
 
Priority Queue Operations
 
1. insert
2. remove
3. check empty
4. check full
5. clear
6. size
3
 
Empty Status : true
 
Do you want to continue (Type y or n)
 
y
 
Priority Queue Operations
 
1. insert
2. remove
3. check empty
4. check full
5. clear
6. size
6
 
Size = 0
 
Do you want to continue (Type y or n)
 
n

To practice programs on every topic in Java, please visit “Programming Examples in Java”, “Data Structures in Java” and “Algorithms in Java”.

advertisement

Next Steps:

Related Posts:

advertisement

Recommended Articles:

  1. Java Program to Implement Meldable Heap
  2. Java Program to Implement Queue Using Two Stacks
  3. Java Program to Implement Leftist Heap
  4. Java Program to Implement Fibonacci Heap
  5. Java Program to Implement Skew Heap
  6. Java Program to Implement Circular Buffer
  7. Java Program to Implement D-ary Heap
  8. Java Program to Implement Queue using Linked List
  9. Java Program to Implement Binary Heap
  10. Java Program to Implement Ternary Heap
advertisement
Additional Resources:

Popular Pages:

Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.