Priority queue

A priority queue is an abstract data type supporting the following two operations:

• add an element to the queue with an associated priority
• remove the element from the queue that has the highest priority, and return it

The simplest way to implement a priority queue is with an array of records containing elements and priorities, along with a count that tells how many elements of the array are used; adding an element involves incrementing that count and writing the new element and priority into the previously unused slot; removing the element requires searching through the array for the element with the highest priority, copying the last element into its slot, and decrementing that count.

This makes removing an element O(n) in the number of elements in the queue, which is somewhat inefficient if the queue gets large; a heap is a more efficient way to implement a priority queue for a large number of elements.

See also: scheduling