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 process
es in an operating system
or the interactions in a simulation
. Some graph algorithm
s 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.