Java Program to Implement Priority Queue

«
»
This is a Java Program to implement Priority Queue. A priority queue is an abstract data type which is like a regular queue or stack data structure, but where additionally each element has a “priority” associated with it. 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.

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.

  1. /**
  2.  ** Java Program to implement Priority Queue
  3.  **/
  4.  
  5. import java.util.Scanner;
  6.  
  7. /** class Task **/
  8. class Task
  9. {
  10.     String job;
  11.     int priority;
  12.  
  13.     /** Constructor **/
  14.     public Task(String job, int priority)
  15.     {
  16.         this.job = job;
  17.         this.priority = priority; 
  18.     }
  19.     /** toString() **/
  20.     public String toString() 
  21.     {
  22.         return "Job Name : "+ job +"\nPriority : "+ priority;
  23.     }
  24. }
  25.  
  26. /** Class PriorityQueue **/
  27. class PriorityQueue
  28. {
  29.     private Task[] heap; 
  30.     private int heapSize, capacity;
  31.  
  32.     /** Constructor **/
  33.     public PriorityQueue(int capacity)
  34.     {    
  35.         this.capacity = capacity + 1;
  36.         heap = new Task[this.capacity];
  37.         heapSize = 0;
  38.     }
  39.     /** function to clear **/
  40.     public void clear()
  41.     {
  42.         heap = new Task[capacity];
  43.         heapSize = 0;
  44.     }
  45.     /** function to check if empty **/
  46.     public boolean isEmpty()
  47.     {
  48.         return heapSize == 0;
  49.     }
  50.     /** function to check if full **/
  51.     public boolean isFull()
  52.     {
  53.         return heapSize == capacity - 1;
  54.     }
  55.     /** function to get Size **/
  56.     public int size()
  57.     {
  58.         return heapSize;
  59.     }
  60.     /** function to insert task **/
  61.     public void insert(String job, int priority)
  62.     {
  63.         Task newJob = new Task(job, priority);
  64.  
  65.         heap[++heapSize] = newJob;
  66.         int pos = heapSize;
  67.         while (pos != 1 && newJob.priority > heap[pos/2].priority)
  68.         {
  69.             heap[pos] = heap[pos/2];
  70.             pos /=2;
  71.         }
  72.         heap[pos] = newJob;    
  73.     }
  74.     /** function to remove task **/
  75.     public Task remove()
  76.     {
  77.         int parent, child;
  78.         Task item, temp;
  79.         if (isEmpty() )
  80.         {
  81.             System.out.println("Heap is empty");
  82.             return null;
  83.         }
  84.  
  85.         item = heap[1];
  86.         temp = heap[heapSize--];
  87.  
  88.         parent = 1;
  89.         child = 2;
  90.         while (child <= heapSize)
  91.         {
  92.             if (child < heapSize && heap[child].priority < heap[child + 1].priority)
  93.                 child++;
  94.             if (temp.priority >= heap[child].priority)
  95.                 break;
  96.  
  97.             heap[parent] = heap[child];
  98.             parent = child;
  99.             child *= 2;
  100.         }
  101.         heap[parent] = temp;
  102.  
  103.         return item;
  104.     }
  105. }
  106.  
  107. /** Class PriorityQueueTest **/
  108. public class PriorityQueueTest
  109. {
  110.     public static void main(String[] args)
  111.     {
  112.         Scanner scan = new Scanner(System.in);
  113.         System.out.println("Priority Queue Test\n");   
  114.  
  115.         System.out.println("Enter size of priority queue ");
  116.         PriorityQueue pq = new PriorityQueue(scan.nextInt() );
  117.  
  118.         char ch;
  119.         /*  Perform Priority Queue operations */
  120.         do    
  121.         {
  122.             System.out.println("\nPriority Queue Operations\n");
  123.             System.out.println("1. insert");
  124.             System.out.println("2. remove");
  125.             System.out.println("3. check empty");
  126.             System.out.println("4. check full");
  127.             System.out.println("5. clear");
  128.             System.out.println("6. size");
  129.  
  130.             int choice = scan.nextInt();            
  131.             switch (choice) 
  132.             {
  133.             case 1 : 
  134.                 System.out.println("Enter job name and priority");
  135.                 pq.insert(scan.next(), scan.nextInt() );                     
  136.                 break;                          
  137.             case 2 : 
  138.                 System.out.println("\nJob removed \n\n"+ pq.remove()); 
  139.                 break;        
  140.             case 3 : 
  141.                 System.out.println("\nEmpty Status : "+ pq.isEmpty() );
  142.                 break; 
  143.             case 4 : 
  144.                 System.out.println("\nFull Status : "+ pq.isFull() );
  145.                 break; 
  146.             case 5 : 
  147.                 System.out.println("\nPriority Queue Cleared");
  148.                 pq.clear();
  149.                 break;    
  150.             case 6 : 
  151.                 System.out.println("\nSize = "+ pq.size() );
  152.                 break;         
  153.             default : 
  154.                 System.out.println("Wrong Entry \n ");
  155.                 break;   
  156.             }    
  157.  
  158.             System.out.println("\nDo you want to continue (Type y or n) \n");
  159.             ch = scan.next().charAt(0);                        
  160.         } while (ch == 'Y'|| ch == 'y');            
  161.     }
  162. }

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

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
advertisement
advertisement
If you wish to look at all Java Programming examples, go to Java Programs.

Next Steps:

Related Posts:

advertisement

Recommended Articles:

  1. Java Program to Implement Queue
  2. Java Program to Implement Queue Using Two Stacks
  3. Java Program to Implement Queue using Linked List
  4. Java Program to Implement Meldable Heap
  5. Java Program to Implement Heap
  6. Java Program to Implement D-ary Heap
  7. Java Program to Implement Ternary Heap
  8. Java Program to Implement Doubly Ended Queue
  9. Java Program to Implement Binary Heap
  10. Java Program to Implement Heap Sort using a Priority Queue
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.