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.