Priority queue

related topics
{math, number, function}
{system, computer, user}
{rate, high, increase}

A priority queue is an abstract data type in computer programming that supports the following three operations:

  • insertWithPriority: add an element to the queue with an associated priority
  • getNext: remove the element from the queue that has the highest priority, and return it (also known as "PopElement(Off)", or "GetMinimum")
  • peekAtNext (optional): look at the element with highest priority without removing it.

For an analogy, see the Implementation section below.


Similarity to queues

One can imagine a priority queue as a modified queue, but when one would get the next element off the queue, the highest-priority one is retrieved first.

Stacks and queues may be modeled as particular kinds of priority queues. In a stack, the priority of each inserted element is monotonically increasing; thus, the last element inserted is always the first retrieved. In a queue, the priority of each inserted element is monotonically decreasing; thus, the first element inserted is always the first retrieved.


Simple implementations

There are a variety of simple, usually inefficient, ways to implement a priority queue. They provide an analogy to help one understand what a priority queue is:

  • Sorted list implementation: Like a checkout line at the supermarket, but where important people get to "cut" in front of less important people. (O(n) insertion time, O(1) get-next time, O(n*log(n)) to build)
  • Unsorted list implementation: Keep a list of elements as the queue. To add an element, append it to the end. To get the next element, search through all elements for the one with the highest priority. (O(1) insertion time, O(n) get-next due to search)

Full article ▸

related documents
Java Servlet
Fourth-generation programming language
Wikipedia:Free On-line Dictionary of Computing/E - H
Maple (software)
Event-driven programming
Queueing theory
Enterprise Objects Framework
Emacs Lisp
Wikipedia:Free On-line Dictionary of Computing/symbols - B
Amdahl's law
Ada (programming language)
.NET Framework
Compiler optimization
Locality of reference
Parrot virtual machine
Microsoft Access
Wikipedia:Free On-line Dictionary of Computing/L - N
Ladder logic
Linear feedback shift register