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.