A priority queue is a special type of queue in which each element is associated with a priority value. And, elements are served on the basis of their priority. That is, higher priority elements are served first.
However, if elements with the same priority occur, they are served according to their order in the queue.
Assigning Priority Value
Generally, the value of the element itself is considered for assigning the priority. For example,
The element with the highest value is considered the highest priority element. However, in other cases, we can assume the element with the lowest value as the highest priority element.
We can also set priorities according to our needs.
Implementation of Priority Queue
Priority queue can be implemented using an array, a linked list, a heap data structure, or a binary search tree. Among these data structures, heap data structure provides an efficient implementation of priority queues.
Hence, we will be using the heap data structure to implement the priority queue in this tutorial. A max-heap is implement is in the following operations. If you want to learn more about it, please visit max-heap and mean-heap.
A comparative analysis of different implementations of priority queue is given below.
Priority Queue Operations
Basic operations of a priority queue are inserting, removing, and peeking elements.
1. Inserting an Element into the Priority Queue
2. Deleting an Element from the Priority Queue
3. Peeking from the Priority Queue (Find max/min)
