#Collections: Part 3- All about PriorityQueue in Java

ALSO CHECK: Java Collections Interview Questions and Answers

What is PriorityQueue in Java?

• A queue follows First-In-First-Out algorithm, in case of PriorityQueue queue elements are processed according to the priority (ordered as per their natural ordering or based on a custom Comparator supplied at the time of creation).
• The PriorityQueue is based on the priority heap.
• We can’t create PriorityQueue of Objects that are non-comparable
• Inserting null into a PriorityQueue will throw a NullPointerException, as PriorityQueue in Java does not permit null elements.
• PriorityQueue are unbound queues.
• The head of this queue is the least element with respect to the specified ordering. If multiple elements are tied for least value, the head is one of those elements — ties are broken arbitrarily.
• The queue retrieval operations poll, remove, peek, and element access the element at the head of the queue.
• PriorityQueue inherits methods from AbstractQueue, AbstractCollection, Collection and Object class.
• Inserting an element (offer()) and deleting an element (poll()) in a PriorityQueue both have a time complexity of O(log n), where n is the number of elements in the queue.
• The default PriorityQueue is implemented with Min-Heap, which means the top element is the minimum one in the heap. If we want to implement a max-heap, we need to use our custom Comparator.
• Internally, the PriorityQueue in Java uses an array to store its elements. This array automatically grows in size if the initial capacity (which is 11 by default in JDK 17) is not large enough to hold all the elements added to the queue. 
• While you don't have to specify an initial capacity when creating a PriorityQueue, if you know how many elements you'll be adding ahead of time, it's beneficial to set an initial capacity. This helps prevent the queue from frequently resizing, which can use up unnecessary CPU resources that could be better utilized elsewhere.

Can you provide an example scenario where a PriorityQueue would be useful?

A PriorityQueue can be used in scenarios such as task scheduling in an operating system, where tasks with higher priority need to be executed before those with lower priority.

PriorityQueue Constructors

• PriorityQueue(): Creates a PriorityQueue with the default initial capacity (which is 11) that orders its elements according to their natural ordering.
• PriorityQueue(Collection c): It creates a PriorityQueue containing the elements in the specified collection.
• PriorityQueue(int initialCapacity): Creates a PriorityQueue with the specified initial capacity that orders its elements according to their natural ordering.
• PriorityQueue(int initialCapacity, Comparator comparator): Creates a PriorityQueue with the specified initial capacity that orders its elements according to the specified comparator.
• PriorityQueue(PriorityQueue c): Creates a PriorityQueue containing the elements in another priority queue.
• PriorityQueue(SortedSet c): Creates a PriorityQueue containing the elements in the specified sorted set.

PriorityQueue operations

• boolean add(E element)inserts the specified element into this priority queue.
• boolean offer(E e) method is used to insert a specific element into the priority queue.
• public peek() retrieves, but does not remove, the head of this queue, or returns null if this queue is empty.
• public poll() retrieves and removes the head of this queue, or returns null if this queue is empty.
• public remove() removes a single instance of the specified element from this queue, if it is present. When we remove an element from the priority queue, the least element according to the specified ordering is removed first.
• Iterator iterator() returns an iterator over the elements in this queue.
• boolean contains(Object o) method returns true if this queue contains the specified element
• void clear() is used to remove all of the contents of the priority queue.
• int size() returns the number of elements present in the set.
• toArray() is used to return an array containing all of the elements in this queue.
• Comparator comparator() method is used to return the comparator that can be used to order the elements of the queue.

What is the difference between offer and add methods of PriorityQueue?

• offer() and add() are two ways to insert data into a PriorityQueue.
• In Queues, the add is used to insert a specified element into the queue. It returns true when the task is successful or else it throws an exception. offer() is also used to insert a specified element into the queue. But it returns true when the task is successful or else its return false.
• In the case of PriorityQueue, the add method behaves identically to offer() in a PriorityQueue. If you see the implementation, the add method of PriorityQueue is internally calling offer.

GIT URL: PriorityQueue Example in Java

Priority Queue Example

-K Himaanshu Shuklaa..