# priority queue

(data structure)

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.

1. new() returns a priority queue
2. min(insert(v, new())) = v
3. dm(insert(v, new())) = new()
4. min(insert(v, insert(w, PQ))) = if priority(v) < priority(min(insert(w, PQ))) then v else min(insert(w, PQ))
5. dm(insert(v, insert(w, PQ))) = if priority(v) < priority(min(insert(w, PQ))) then insert(w, PQ) else insert(v, dm(insert(w, PQ)))
where PQ is a priority queue, v and w are items, and priority(v) is the priority of item v.

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.

Note: It can be implemented efficiently with a heap. After LK.

Author: PEB

## Implementation

Links to implementations, dozens of papers, introductory material, etc..

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