Priority Queue

Java PriorityQueue

PriorityQueue belongs to the Java Collections Framework. PriorityQueue is based on  priority heap and it is an implementation of Queue interface. This data structure can be used when we need a Queue implementation and we have a requirement to maintain the elements of that collection in a specific sorted order based on each element’s priority. It was introduced in JDK 1.5

Java PriorityQueue Key points

• A Comparator can be provided in the constructor when instantiating a PriorityQueue. Then the order of the items in the Queue will be decided based on the Comparator provided.
• If a Comparator is not provided, then the natural order (Comparable) of the Collection will be used to order the elements.
• null is not allowed in this Collection.
• Head of the Queue is the least item in the order.
• Ordering ties between the PriorityQueue elements are decided arbitrarily.
• PriorityQueue is not synchronized. PriorityBlockingQueue is the thread-safe counterpart of PriorityQueue.
• PriorityQueue is unbounded and it grows dynamically based on the number of elements in the Queue. It has internal capacity at any given time and it is increased as the elements are added. The policy for this internal capacity and increment is not specified or standardized.
• The iterator() of this PriorityQueue does not guarantee for traversal of the Queue elements in any particular order.
• Performance wise; remove() and contains() methods take linear time. peek(), element() and size() takes fixed time. offer(), poll() and remove() takes O(log n) time.
• offer() and add() are methods of the Queue interface and implemented by the PriorityQueue. These are used of element insertion in the queue. They behave the same with respect to PriorityQueue and no difference between them.

PriorityQueue Example

Following example explains how we can use a Java PriorityQueue collection.

PriorityQueueExample.java

package com.javapapers.java;

import java.util.Comparator;
import java.util.PriorityQueue;

public class PriorityQueueExample {
 public static void main(String[] args) {
  Comparator<String> queueComparator = new VowelComparator();
  PriorityQueue<String> priorityQueue = new PriorityQueue<String>(10,
    queueComparator);
  priorityQueue.add("orange");
  priorityQueue.add("fig");
  priorityQueue.add("watermelon");
  priorityQueue.add("lemon");
  while (priorityQueue.size() != 0) {
   System.out.println(priorityQueue.remove());
  }
 }
}

VowelComparator.java

This Comparator class is used to determine the sort order of the above PriorityQueue.

package com.javapapers.java;

import java.util.Comparator;

class VowelComparator implements Comparator<String> {

 @Override
 public int compare(String x, String y) {
  if (getVowelCount(x) < getVowelCount(y)) {
   return -1;
  } else if (getVowelCount(x) > getVowelCount(y)) {
   return 1;
  }
  return 0;
 }

 public int getVowelCount(String word) {
  int vowel = 0;
  for (int i = 0; i < word.length(); i++) {
   char chr = word.charAt(i);
   if (chr == 'a' || chr == 'A' || chr == 'e' || chr == 'E'
     || chr == 'i' || chr == 'I' || chr == 'o' || chr == 'O'
     || chr == 'u' || chr == 'U')
    vowel++;
  }
  return vowel;
 }
}

PriorityQueue Example Output

fig
lemon
orange
watermelon