 # 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..