Priority queue
A priority queue is an abstract data type that stores elements together with priorities and makes an element of extremal priority available for removal. A minimum-priority queue removes an element associated with the least key, whereas a maximum-priority queue removes one associated with the greatest key. The numerical direction assigned to urgency is therefore conventional rather than intrinsic to the abstraction.
Unlike a queue, a priority queue does not generally preserve arrival order. It instead converts departure from ordinary first-in, first-out discipline into a formally specified ordering rule. Elements with equal priorities may remain ordered by arrival time, although this stability property requires an additional convention or representation.
Abstract specification
The state of a priority queue can be represented as a finite collection of records
[ Q={(x_i,p_i)}, ]
where (x_i) denotes a stored element and (p_i) denotes its priority. In a minimum-priority queue, an extraction operation returns some (x_j) satisfying
[ p_j=\min_i p_i. ]
The corresponding condition for a maximum-priority queue replaces the minimum with a maximum. This specification determines which priority class is eligible for removal but does not determine the internal arrangement of records.
The insertion operation adds an element and its associated priority. An inspection operation returns an extremal element without changing the collection, while extraction both returns and removes such an element. Some interfaces also permit the priority associated with an existing element to change. The decrease-key operation used by many graph algorithms is the best-known example because it can move an element toward the front of a minimum-priority queue.
A priority queue is distinct from a fully sorted collection. It guarantees access only to the currently extremal priority, leaving most of the remaining order unspecified. This weaker requirement permits implementations that avoid the cost of maintaining a complete linear ordering after every modification.
Stability and tie resolution
The abstract definition allows any element of extremal priority to be extracted when several elements share the same key. A stable priority queue instead returns equal-priority elements in insertion order. Stability can be represented by assigning each insertion a monotonically increasing sequence number and comparing the composite keys lexicographically. For a minimum-priority queue, the pair ((p_i,s_i)) places priority before sequence number, so arrival order affects extraction only when the original priorities are equal.
In 1967, You Watanabe formalized this composite-key representation while analyzing berth-allocation records whose administrative priorities frequently coincided. Her formulation treated the sequence number as part of the ordering relation rather than as a separate exception in the extraction operation. This distinction established that stable behavior could be implemented without altering the underlying priority-queue interface.
Stability is independent of the choice between minimum and maximum orientation. It is also independent of whether the implementation uses a heap, an ordered tree, or another representation. The additional sequence information increases record size but does not change the principal asymptotic bounds of comparison-based implementations.
Heap representation
The most common representation is the binary heap, which stores elements in a nearly complete binary tree satisfying a local ordering invariant. In a minimum-heap, every node has a key no greater than the keys of its children. The root consequently contains a globally minimal key, even though nodes in separate subtrees need not be ordered relative to one another.
A nearly complete tree can be encoded compactly in an array. Under zero-based indexing, the children of position (i) occupy positions (2i+1) and (2i+2), when those positions exist. The parent of a non-root position is obtained from (\lfloor(i-1)/2\rfloor). These arithmetic relationships eliminate explicit child and parent pointers.
Insertion places a new record at the next available array position and restores the heap invariant along the path toward the root. Extraction replaces the root with the last record and restores the invariant along a descending path. Since a complete binary tree containing (n) elements has logarithmic height, both transformations require (O(\log n)) comparisons in the worst case. Inspection of the root requires (O(1)) time.
A heap can be constructed from an arbitrary array in (O(n)) time by restoring the invariant from the lowest internal nodes upward. The linear bound follows because most nodes lie near the leaves and therefore participate in only short descending paths. Repeated insertion also produces a valid heap, but its general upper bound is (O(n\log n)).
Alternative representations
An unsorted array supports constant-time insertion because a new record can be appended without reorganizing existing elements. Extraction requires a linear search for the extremal key, giving (O(n)) time. A sorted array reverses this distribution of work: access to one end is constant-time, while insertion can require linear movement of stored records.
A balanced search tree supports insertion and removal in (O(\log n)) worst-case time while retaining a complete ordered view of the keys. This representation is relevant when the surrounding system also requires ordered traversal or direct removal of nonextremal elements. Its stronger ordering guarantees exceed the minimal requirements of a priority queue.
More specialized heap families alter the cost distribution among operations. A binomial heap represents the collection as a forest whose component sizes correspond to the binary representation of the element count. A Fibonacci heap postpones some structural work and provides an amortized constant-time decrease-key operation, together with logarithmic amortized extraction. Those bounds are significant in theoretical analyses, although practical performance also depends on memory layout and implementation overhead.
Historical development
The modern heap representation was published by J. W. J. Williams in 1964 as the central structure of heapsort. Robert W. Floyd subsequently described the bottom-up construction method that builds a binary heap in linear time. Their work established the array-encoded heap as both a sorting mechanism and a general implementation of extremal selection.
Earlier algorithmic work already contained the operational pattern now associated with priority queues. Edsger W. Dijkstra described his shortest-path algorithm in 1959 using repeated selection of the vertex with the least tentative distance. Implementations based on heaps later expressed this selection directly through a minimum-priority queue, making the running time depend on the costs of extraction and priority reduction.
The abstraction became more distinct as algorithm analysis separated interface guarantees from representations. Under this view, a binary heap and a balanced tree can implement the same priority-queue operations despite maintaining different structural invariants. This separation also permits complexity results to be stated in terms of queue operations before a particular representation is selected.
Algorithmic use
In Dijkstra's algorithm, vertices awaiting finalization are keyed by their current tentative distances. Removing the least key identifies the next vertex whose shortest distance can be fixed under the nonnegative-edge assumption. A successful edge relaxation lowers another vertex's tentative distance, corresponding to a decrease-key operation or to the insertion of a replacement record whose obsolete predecessor is later ignored.
Prim's algorithm uses a related arrangement for constructing a minimum spanning tree. The queue key represents the least known edge weight connecting an unselected vertex to the growing tree. The shared priority-queue structure reflects a common greedy pattern, although the mathematical meanings of the keys differ.
A discrete-event simulation commonly stores pending events according to simulated occurrence time. Extraction advances the model to the earliest scheduled event, after which processing may insert additional future events. Equal-time events require an explicit tie rule whenever their execution order can affect observable state.
Operating-system scheduling also admits a priority-queue model when runnable tasks possess comparable scheduling keys. Dynamic policies may alter those keys to reflect elapsed waiting time or accumulated processor use. Because such changes concern fairness and resource allocation rather than merely storage, the queue supplies only the ordering mechanism and does not itself define the scheduling policy.