The Priority Queue ADT
The Priority Queue is an abstract data type similar to the Queue data type in which each element additionally has a priority associated with it. In a priority queue, an element with high priority is served before an element with low priority.
In some implementations, if two elements have the same priority, they are served according to the order in which they were enqueued, while in other implementations, ordering of the elements with the same priority is undefined.
Priority Queue Operations:
- Enqueue (data, priority)
- Dequeue ()
Enqueue (data, priority) — This will insert element with its priority into the priority queue.
Dequeue ( ) — This will return the element with the highest priority from the priority queue.
A naive implementation is to keep all elements with their priorities in an unsorted list and go through the list to look for the element with the highest priority whenever the highest priority element is requested.
In this case, Enqueue operation will be done in constant time while the Dequeue will be done in linear time.
The usual implementation is to use the heap datastructure to improve performance. The heap uses O(log n) for inserts/removals and O(n) to build the priority queue initially from a list of n elements.
Real life Applications
- Operating System Task Scheduler — Some tasks are more important than others to the operating systems and the priority queue is best for this.