What is a priority queue?

In some situations we might need to find the minimum/maximum element among a collection of elements. Priority Queue ADT is the one which supports these kind of operations. A priority queue ADT is a data structure that supports the operations Insert and DeleteMin (which returns and removes the minimum element) or DeleteMax (which returns and removes the maximum element).

These operations are equivalent to EnQueue and DeQueue operations of a queue. The difference is that, in priority queues, the order in which the elements enter the queue may not be same in which they were processed. An example application of a priority queue is job scheduling, which is prioritized instead of serving on the basis of first come first serve.

A priority queue is called an ascending – priority queue, if the item with smallest key has the highest priority (that means, delete smallest element always). Similarly, a priority queue is said to be a descending – priority queue if the item with largest key has the highest priority (delete maximum element always). Since these two types are symmetric we can study any of these. The other one can be implemented in a similar manner.

Applications of a Priority Queue:-

• Data Comparison: Huffman Coding Algorithm
• Shortest path algorithm: Dijkstra’s Algorithm
• Minimum spanning tree algorithm: Prim’s Algorithm
• Event-driven simulation: customers in a line
• Selection problem: Finding k^th smallest element

Priority Queue Operations:-

• Insert (key, data): Inserts data with key to the priority queue. Elements are ordered based on key.
• DeleteMin/DeleteMax: Remove and return the element with the smallest/largest key.
• GetMinimum/GetMaximum: Return the element with the smallest/largest key without deleting it.
• k^th smallest/largest: Get the k^th smallest/largest element
• Size: Returns the size of the priority queue
• Heap Sort: Sorts the elements in the priority queue based on priority(key).