Encyclopedia > Priority queue

  Article Content

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



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
Quadratic formula

... Generalizations The formula and its proof remain correct if ...

 
 
 
This page was created in 37.5 ms