Priority Queue

Priority Queue is an upgraded version of the data structure queue. Queue is a simple data structure which follows a simple First In First Out (FIFO) rule in order to perform operations on its elements.

Whereas Priority Queue as the name suggests performs different operations on the elements based on the priority. Sometimes when the elements of the queue need to be processed according to the priority, that’s when the Priority Queue comes into play.

The Priority Queue is based on the priority heap. The elements of the priority queue are ordered according to the natural ordering, or by a Comparator provided at queue construction time, depending on which constructor is used.

Few key points to remember:

1. Priority Queue doesn’t permit null.
2. We can’t create Priority Queue of Objects that are non- comparable
3. Priority Queue are unbound queues.
4. The queue retrieval operations poll, remove, peek, and element access the element at the head of the queue.
5. It provides O(log(n)) time for add and poll methods.

Syntax for creating priority queue:

1. PriorityQueue(): Creates a PriorityQueue with the default initial capacity (11) that orders its elements according to their natural ordering.
2. PriorityQueue(Collection c): Creates a PriorityQueue containing the elements in the specified collection.

Applications of Priority Queue:

1. CPU Scheduling
2. Graph algorithms like Dijkstra’s shortest path algorithm, Prim’s Minimum Spanning Tree.
3. All queue applications where priority is involved.