Priority Queue in Java

In this article, I am going to describe how the priority queue is developed in Java.

Introduction

 
In this article, we are going to describe how the priority queue is developed in Java. In Java you can easily make a priority queue with the help of the Java API. Java a sprat class named PriorityQueue. The PriorityQueue class implements the Queue interface. When items are added to a PriorityQueue they are not ordered by First In, First Out. Instead, all items in a PriorityQueue must be comparable (either by implementing the Comparable interface or by a Comparator) which is used to sort the items in the list.
 

PriorityQueue in Java

 
A priority queue is a collection of elements in which each element has been assigned a priority and depending on that order each element is deleted and processed depending on the following rules:
  • An element of higher priority is processed before any element of lower priority.
  • Two elements with the same priority are processed according to the order in which they were added to the queue.
queue_line_2.jpg
 
A PriorityQueue is a queue where a sorted order is permanently imposed on the items it contains; in queue terms, the highest-priority element is at the head of the queue (and the lowest is at the tail of the queue) queue operations are efficient: that is, removing the highest-priority element and adding any element are both efficient operations.
 
Non-queue operations (such as searching for an item that isn't at the head of the queue) are not efficient.
 
Remember that a queue, in general, is essentially a structure optimized to add things to one end and remove them from the other. With a priority queue, we can envisage this queue as a permanently-sorted list, so that the highest priority element is always at one end and the lowest-priority element at the other. In this case, we don't actually add an element to the "end": each element added is automatically slotted into the relevant place in the list depending on its priority.
 
Example
  1. public class PriorityQDemo  
  2. {  
  3.  // array in sorted order, from max at 0 to min at size-1  
  4.  private int maxSize;  
  5.  private long[] queArray;  
  6.  private int nItems;  
  7.  public PriorityQDemo(int s)  
  8.  {  
  9.   maxSize = s;  
  10.   queArray = new long[maxSize];  
  11.   nItems = 0;  
  12.  }  
  13.  public void insert(long item)  
  14.  {  
  15.   int i;  
  16.   if (nItems == 0)  
  17.    // insert at 0  
  18.    queArray[nItems++] = item;  
  19.   else  
  20.   {  
  21.    // start at end,  
  22.    for (i = nItems - 1; i >= 0; i--)  
  23.    {  
  24.     // if new item larger,  
  25.     if (item > queArray[i])  
  26.      // shift upward  
  27.      queArray[i + 1] = queArray[i];  
  28.     else  
  29.      // if smaller,  
  30.      break;  
  31.     // done shifting  
  32.    }  
  33.    queArray[i + 1] = item;  
  34.    // insert it  
  35.    nItems++;  
  36.   } // end else (nItems > 0)  
  37.  }  
  38.  public long remove()  
  39.  {  
  40.   return queArray[--nItems];  
  41.  }  
  42.  public long peekMin()  
  43.  {  
  44.   return queArray[nItems - 1];  
  45.  }  
  46.  public boolean isEmpty()  
  47.  {  
  48.   return (nItems == 0);  
  49.  }  
  50.  public boolean isFull()  
  51.  {  
  52.   return (nItems == maxSize);  
  53.  }  
  54.  public static void main(String[] args)  
  55.  {  
  56.   PriorityQDemo thePQ = new PriorityQDemo(5);  
  57.   thePQ.insert(30);  
  58.   thePQ.insert(50);  
  59.   thePQ.insert(10);  
  60.   thePQ.insert(40);  
  61.   thePQ.insert(20);  
  62.   while (!thePQ.isEmpty())  
  63.   {  
  64.    long item = thePQ.remove();  
  65.    // 10, 20, 30, 40, 50  
  66.    System.out.print(item + " ");  
  67.   }  
  68.   System.out.println("");  
  69.  }  
  70. }  
Output
 
You can see that the insertion order is different and displays in a different order.
 
PriorityQueue in Java
 
Resources