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

... left side is now a perfect square; it is the square of (x + b/(2a)). The right side can be written as a single fraction; the common denominator is 4a2. W ...

This page was created in 36.2 ms