display | more...
A priority queue is a data structure designed to organize a number of objects according to each object's priority. usual operations are:
  • adding an object
  • finding and/or removing the object with the highest priority
  • removing an object (optional)
  • changing an object's priority (optional)
Priority queues are needed for scheduling, e.g. the processes in an operating system or the interactions in a simulation. Some graph algorithms such as Dijkstra's algorithm and Prim's algorithm also use them.

For very small (smaller than about 50 objects) queues, a sorted linked list is actually the best data structure, because of its small overhead. The "typical" priority queue, however, and one that is also fit to handle larger queue sizes, is the heap data structure. For very large queues, Fibonacci heaps are even better.