Post
Ask Question

Priority Queue 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


Similar Articles