PriorityQueue in Java

In Java, a PriorityQueue is a specialized implementation of the Queue interface that allows elements to be processed in a specific order based on their priority level. The priority of an element is determined by its comparison to other elements in the Queue, using a Comparator or the natural ordering of the elements.

Some of the key features of a PriorityQueue in Java

  1. Priority Order: Elements in a PriorityQueue are processed in a specific priority order, as determined by their comparison to other elements in the Queue. The highest-priority element is always processed first.

  2. No Random Access: Unlike some other collections in Java, such as ArrayList or LinkedList, a PriorityQueue does not allow for random access to elements. Instead, elements are processed strictly in their priority order.

  3. Size Limit: A PriorityQueue may have a size limit, meaning that once the maximum number of elements is reached, no further elements can be added until some are removed.

  4. Null Elements: Null elements are not allowed in a PriorityQueue.

  5. Complexity: The time complexity of basic operations such as adding or removing elements from a PriorityQueue is O(log n), making it a relatively efficient data structure for managing large collections of elements.

Methods in PriorityQueue class

  • add(e): This method adds the specified element to the PriorityQueue. If the element already exists in the PriorityQueue, it is not added again.

  • offer(e): This method adds the specified element to the PriorityQueue. If the element cannot be added due to capacity restrictions, it returns false.

  • peek(): This method retrieves, but does not remove, the head of the PriorityQueue. If the PriorityQueue is empty, it returns null.

  • poll(): This method retrieves and removes the head of the PriorityQueue. If the PriorityQueue is empty, it returns null.

  • remove(Object o): This method removes the specified element from the PriorityQueue. If the element is not present, it returns false.

  • clear(): This method removes all elements from the PriorityQueue.

  • size(): This method returns the number of elements in the PriorityQueue.

  • toArray(): This method returns an array containing all elements in the PriorityQueue.

  • iterator(): This method returns an iterator over the elements in the PriorityQueue.

  • comparator(): This method returns the Comparator used to order the elements in the PriorityQueue, or null if the natural ordering is used.

Here's an example of using a PriorityQueue in Java

import java.util.PriorityQueue;
public class PriorityQueueExample {
  public static void main(String[] args) {
    PriorityQueue<String> pq = new PriorityQueue<>((a, b) ->
      a.length() - b.length()
    );
    pq.add("apple");
    pq.add("banana");
    pq.add("pear");
    pq.add("orange");
    while (!pq.isEmpty()) {
      System.out.println(pq.remove());
    }
  }
}

In this example, we create a PriorityQueue that compares elements based on their length using a lambda expression. We then add several strings to the queue, and remove them one-by-one using the remove() method, which always returns the highest-priority element (in this case, the shortest string). The output of this program will be:

pear
apple
banana
orange

Overall, a PriorityQueue in Java is a useful data structure for managing collections of elements in a specific order based on their priority level. By using a Comparator or the natural ordering of the elements, we can ensure that elements are always processed in the correct priority order.