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.

Contents

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.

Implementation

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
Zope
Wikipedia:Free On-line Dictionary of Computing/E - H
AltiVec
Z-buffering
Chmod
Maple (software)
Event-driven programming
Queueing theory
CPAN
Enterprise Objects Framework
Simula
Ext2
ReiserFS
Emacs Lisp
Wikipedia:Free On-line Dictionary of Computing/symbols - B
Amdahl's law
VBScript
Ada (programming language)
.NET Framework
Compiler optimization
REBOL
Locality of reference
Parrot virtual machine
Microsoft Access
Wikipedia:Free On-line Dictionary of Computing/L - N
Ladder logic
Linear feedback shift register
Talker