What is priority queue? Explain the array representation of priority queue.
- A queue in which we are able to insert remove items from any position based on some property (such as priority of the task to be processed) is often referred as priority queue.
- A priority queue is different from a "normal" queue, because instead of being a "first-in-first-out" data structure, values come out in order by priority.
- Below fig. represent a priority queue of jobs waiting to use a computer.
- Priorities of 1, 2, 3 have been attached with jobs of real time, online and batch respectively. Therefore if a job is initiated with priority i, it is inserted immediately at the end of list of other jobs with priorities i. Here jobs are always removed from the front of queue.
Array representation of Priority Queue
- In this approach is to add code for insert to move larger entries one position to the right, thus keeping the entries in the array in order (as in insertion sort).
- Thus the largest item is always at the end, and the code for remove the maximum in the priority queue is the same as for pop in the stack.
One implementation:
- Suppose items with priorities 16, 14, 10, 9, 8, 7, 4, 3, 1 are to be stored in a priority queue.
Suppose an item with priority 15 is added:
Applications of Priority Queue:
- CPU Scheduling
- Graph algorithms like Dijkstra’s shortest path algorithm, Prim’s Minimum Spanning Tree, etc
- All queue applications where priority is involved.
