Priority Queue

A priority queue is a type of queue that arranges elements based on their priority values. Elements with higher priority values are typically retrieved before elements with lower priority values.
If we add an element with a high priority value to a priority queue, it may be inserted near the front of the queue, while an element with a low priority value may be inserted near the back.

Types of Priority Queue:

• Descending Order Priority Queue Max Heap: Higher Priority values are given more priority as compared to Lower Priority values.
• Ascending Order Priority Queue or Min Heap: Lower Priority values are given more priority as compared to Higher Priority values.

Properties of Priority Queue:

• Every item has a priority associated with it.
• An element with high priority is dequeued before an element with low priority.
• If two elements have the same priority, they are served according to their order in the queue.

In the below priority queue, an element with a maximum ASCII value will have the highest priority. The elements with higher priority are served first. 

Operations on Priority Queue:

• Insertion in a Priority Queue: When a new element is inserted in a priority queue, it is placed after the last element and is swapped with the parent node if the order is incorrect. The swapping process continues until all the elements are placed in the correct position. The time complexity is O(logN), where N is the number of elements in the priority queue.
• Deletion in a Priority Queue: It will remove the element which has maximum priority first. This removal creates an empty slot, which will be further filled with new insertion. Then, it compares the newly inserted element with all the elements inside the queue to maintain the heap invariant. The time complexity is O(logN), where N is the number of elements in the priority queue.
• Peek in a Priority Queue: This operation helps to return the maximum element from Max Heap or the minimum element from Min Heap without deleting the node from the priority queue. The time complexity is O(1).

Applications of Priority Queue:

• Dijkstra’s Shortest Path Algorithm using priority queue: When the graph is stored in the form of adjacency list or matrix, priority queue can be used to extract minimum efficiently when implementing Dijkstra’s algorithm. 
• Prim’s algorithm: It is used to implement Prim’s Algorithm to store keys of nodes and extract minimum key node at every step.
• The priority queue (also known as the fringe) is used to keep track of unexplored routes, the one for which a lower bound on the total path length is smallest is given highest priority. 
• Heap Sort: Heap sort is typically implemented using Heap which is an implementation of Priority Queue. 
• Operating systems: It is also used in Operating System for load balancing (load balancing on server), >interrupt handling. 

A Queue is defined as a linear data structure that is open at both ends and the operations are performed in First In First Out (FIFO) order. Queue is a list in which all additions to the list are made at one end, and all deletions from the list are made at the other end.  The element, which is first pushed into the order, the operation is first performed on that.