Priority Queue Class in Java

Introduction

As the name suggests, this data structure implements the algorithm of a queue but processes the objects based on the priority. Fundamentally, these are Queues that follow the First In First Out principle if no priority is mentioned. If some of the objects of the queue are associated with a higher priority, even though the object might be placed at the end of the queue, it will be executed first. The working of the priority queue is based on the Priority heap. When constructing the queue, the elements are either ordered naturally or by a comparator.

Declaration

public class PriorityQueue <E> extends AbstractQueue implements Serializable, where E is the object or element type of the queue.

Priority Queue Features

  • Elements cannot be null in a Priority Queue.
  • If objects are non-comparable, Priority Queues of such objects cannot be created.
  • These are unbound queues, that is, do not have fixed sizes.
  • If there are priority ties between several elements, the tie is broken by arbitrarily processing any of the concerned objects.
  • Time complexity of adding and polling methods is O(log(n))

Constructors

  • PriorityQueue() – Creates an empty priority queue with a default capacity of 11. The elements are ordered according to the natural order.
  • PriorityQueue (Collection <E> c) – Creates an empty priority queue and populates it with the elements of the Collection c.
  • PriorityQueue (int capacity) – Creates a Priority Queue with an initial capacity.
  • PriorityQueue (int initialCapacity, Comparator <E> comparator) – Creates a queue with the initial capacity and orders the elements according to the specified comparator.

Example

import java.util.*;
class DemoPQueue
{
public static void main (String args [])
{
PriorityQueue <Integer> pq = new PriorityQueue <Integer> ();

pq.add(10);
pq.add(20);
pq.add(15);
System.out.println (pq.peek());
System.out. println(pq.poll());
System.out.println(pq.peek());
}
}

OUTPUT

10
10
15

Leave a comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.