Definition: An abstract data type to efficiently support finding the item with the highest priority across a series of operations. The basic operations are: insert, find-minimum (or maximum), and delete-minimum (or maximum). Some implementations also efficiently support join two priority queues (meld), delete an arbitrary item, and increase the priority of a item (decrease-key).
Formal Definition: The operations new(), insert(v, PQ), find-minimum or min(PQ), and delete-minimum or dm(PQ) may be defined with axiomatic semantics as follows.
Generalization (I am a kind of ...)
abstract data type.
Specialization (... is a kind of me.)
pagoda, leftist tree, van Emde-Boas priority queue.
Aggregate parent (I am a part of or used in ...)
best-first search, Dijkstra's algorithm.
Aggregate child (... is a part of or used in me.)
heap, Fibonacci heap.
See also discrete interval encoding tree, hash heap, calendar queue, queue.
Note: It can be implemented efficiently with a heap. After LK.
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 20 December 2004.
HTML page formatted Tue Dec 6 16:16:32 2011.
Cite this as:
Paul E. Black, "priority queue", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 20 December 2004. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/priorityque.html