Priority Queue

Priority Queue

A Priority Queue is a collection of elements such that each element has been assigned a priority and such that the order in which elements are deleted and processed comes from the following rules;

(a) An element of high priority is processed before any element of lower priority.

(b) Two elements with the same priority are processed according to the order in which they were added to the queue.

Priority Queue is more specialized data structure than Queue. It is different from a “normal” queue because instead of being a “first-in-first-out” data structure, values come out in order by priority. In computer science, a priority queue is an abstract data type which is like a regular queue or stack data structure, but where additionally each element has a “priority” associated with it.

Priority Queue is an extension of a queue with the following properties.

  • Every item has a priority associated with it.
  • An element with high priority is dequeued before an element with low priority.
  • If two elements have the same priority, they are served according to their order in the queue.

Applications: CPU Scheduling, Graph algorithms like Dijkstra’s shortest path algorithm, Prim’s Minimum Spanning Tree, etc.