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
Kings Park, New York

... of 18, 5.7% from 18 to 24, 31.9% from 25 to 44, 23.3% from 45 to 64, and 13.9% who are 65 years of age or older. The median age is 38 years. For every 100 females th ...

 
 
 
This page was created in 45.1 ms