Priority Queue is a linear data structure that has the priority associated with each element. So, the elements are served in the order of highest to lowest priority. If multiple elements have the same priority, they are served as per their original order.
Representation
Ordered Queue (for Faster Deletion)
The elements are enqueued in the order of 10, 20, 30, 40, and 50. They are sorted as per their priority during the Enqueue operation. So, the highest priority element is quickly served by the Dequeue operation from the Front side.
Unordered Queue (for Faster Insertion)
The enqueue order 10, 20, 30, 40, and 50 is retained in the Unordered queue as shown below. The dequeue operation serves the highest priority element by searching the entire Queue. So, the dequeue operation is costlier than the enqueue operation.
Properties
- Front: Front side of the queue
- Rear: Rear side of the queue
- Element: The actual data (represented as 50, 20, 40, 10, and 30)
- Priority: Priority of the element (represented as 1-High, 2-Mid, and 3-Low)
- Index: Array index
Priority Queue Operations and Time Complexity
| Operation | Short Description | Time Complexity Ordered | Time Complexity Unordered | Space Complexity |
|---|---|---|---|---|
| Enqueue | Insert a new element | O(n) | O(1) | O(n) |
| Dequeue | Delete the element | O(1) | O(n) | O(n) |
| Peek | Returns the front element without removing | O(1) | O(n) | O(n) |
| IsFull | Check if the Queue is full | O(1) | O(1) | O(n) |
| IsEmpty | Check if the Queue is empty | O(1) | O(1) | O(n) |
| Search | Search the element by value | O(n) | O(n) | O(n) |
Implementations of Priority Queue
Priority Queue can be implemented using Array, Linked List, or Heap. However, we need to choose the right implementation based on the requirements.
| Implementation | When to Use |
| Priority Queue Implementation using ordered Array | Prefer to work with a fixed amount of data. Also to support faster retrieval or dequeue operation. |
| Priority Queue Implementation using unordered Array | To work with a fixed amount of data. Faster to enqueue the elements but slower to dequeue. |
| Priority Queue Implementation using ordered Linked List | Alternatively, you can prefer linked list implementation to work with large and dynamic data. Use an ordered linked list for faster dequeue operation. |
| Priority Queue Implementation using unordered Linked List | To work with large and dynamic data. Faster to enqueue the elements but slower to dequeue. |
Advantages and Disadvantages
Advantages
- Priority Queue is unique and can serve the elements based on their priority.
Disadvantages
- The unordered implementation always requires the full search to dequeue the highest priority element.
- Array implementation requires swapping the elements for enqueue or dequeue operation.
Applications of Priority Queue in Data Structure
When to use Priority Queues
Prefer priority queues when your Application wants to provide preference to certain tasks. Also, use priority queues when you have limited resources shared by multiple tasks.
Realtime Applications
- CPU Scheduling & Interrupt Handling – Operating systems use priority queues to execute high-priority tasks first. So, the interrupt requests are enqueued with high priority.
- Load Balancing is another application of priority queues. This helps to distribute the load based on priorities.
- Huffman Coding – A data compression algorithm that requires a priority queue to work.