A priority queue is an abstract data type that stores elements with associated priorities and provides access to an element with the highest priority under a specified ordering. Unlike an ordinary queue, which normally removes elements in first-in, first-out order, a priority queue selects elements by priority. It is a fundamental component of graph algorithms, scheduling systems, and event-driven simulations. A priority queue describes an interface and its behavior; a heap is one possible implementation, not a synonym for the abstraction.
Ordering and basic operations
A priority queue usually takes one of two forms:
- A min-priority queue returns an element with the smallest key.
- A max-priority queue returns an element with the largest key.
Here, a key is the value used to determine priority. The word “highest” therefore refers to precedence, not necessarily to the largest numerical value: a task with priority number 1 may precede a task with priority number 5.
The basic operations are:
| Operation | Meaning |
|---|---|
insert(item, key) |
Add an element with a specified priority |
peek() or find-min() / find-max() |
Return a highest-priority element without removing it |
extract-min() / extract-max() |
Remove and return a highest-priority element |
is-empty() |
Test whether the queue contains any elements |
size() |
Return the number of stored elements |
Some interfaces also support changing an element’s priority, deleting a specified element, or melding two queues. In a min-priority queue, decrease-key improves an element’s priority; in a max-priority queue, increase-key does so.
For example, inserting the pairs , , and into a min-priority queue produces the extraction sequence , regardless of their insertion order.
Ties and stability
Priority queues generally permit multiple elements with equal priorities. Their relative extraction order is unspecified unless the interface explicitly guarantees otherwise.
A stable priority queue preserves insertion order among elements with equal priority. A common implementation assigns each insertion a monotonically increasing sequence number and compares the pair
lexicographically. In a min-priority queue, the earlier insertion then wins a tie. This technique also avoids comparing payload objects when equal priorities occur.
The comparison relation must behave consistently. Many implementations require a strict weak ordering, which allows equivalent keys while maintaining a coherent ordering. Inconsistent comparators, or special values such as floating-point NaN without an explicit ordering policy, can invalidate the structure’s assumptions.
Implementations and complexity
Different data structures implement the same priority-queue interface with different performance trade-offs. The most suitable representation depends on the frequency of insertions, extractions, priority changes, and melds.
For a min-priority queue containing elements, representative time complexities are:
| Representation | Find minimum | Insert | Extract minimum |
|---|---|---|---|
| Unsorted linked list | |||
| Sorted linked list, minimum at head | |||
| Binary heap | |||
| Balanced binary search tree | , or with a cached minimum | ||
| Fibonacci heap | amortized | amortized |
These bounds describe the principal data-structure operations. Dynamic memory allocation, array resizing, and user-defined comparisons can add costs.
An unsorted representation is useful when insertions dominate and minimum extraction is rare. A sorted representation reverses this trade-off. Balanced trees, such as a red–black tree, provide additional capabilities such as ordered traversal and range queries, but typically require more structural overhead than an array-based heap.
Binary heaps
A binary heap is a complete binary tree satisfying a heap-order property. In a min-heap, every parent’s key is no greater than its children’s keys. Consequently, the root contains a minimum element, although the remaining elements are not globally sorted.
The tree is commonly stored in an array. With zero-based indexing, the children of index are at
when those positions exist. For , its parent is at
Insertion appends the new element and repeatedly exchanges it with its parent while heap order is violated. This is called sifting up.
Extraction removes the root, moves the last element into its position, and restores heap order by sifting down, exchanging it with the smaller child as necessary. Both procedures follow a path whose length is at most proportional to the tree’s height, giving time.
An existing array can be converted into a heap in time using bottom-up heap construction. This is faster than the worst-case cost of inserting its elements one at a time. The linear bound arises because most nodes are near the leaves and require little or no downward movement.
Binary heaps use storage and have a compact layout that often benefits cache locality.
Other heap families
Several heap variants optimize different operations:
- -ary heaps give each node up to children. Increasing reduces height but increases the number of child comparisons during downward repair.
- Binomial heaps organize elements into a collection of structured trees and support melding in time.
- Fibonacci heaps support insertion, melding, and decrease-key in amortized time, with amortized minimum extraction.
- Pairing heaps use comparatively simple tree-linking operations and are another option for meldable priority queues.
An amortized bound limits the average cost per operation over a sequence of operations; it is not a guarantee that each individual operation has that cost. Sophisticated asymptotic bounds also do not guarantee faster execution on every workload: allocation, pointer access, comparison cost, and implementation complexity matter.
Changing priorities and locating elements
Finding the minimum is efficient in a heap, but finding an arbitrary element is not. A binary heap alone may require time to locate a particular item.
An indexed priority queue maintains a mapping from element identifiers to heap positions. Whenever two heap entries are exchanged, the mapping is updated. Once an element’s position is known, changing its priority or deleting it takes time in a binary heap. The mapping can use an array for a dense identifier space or a hash table for more general identifiers.
Another approach is lazy invalidation. Rather than updating an existing entry, the program inserts a new entry and marks the old one obsolete, or records the current version separately. Obsolete entries are discarded when encountered during extraction. This avoids a dedicated decrease-key operation but can increase memory consumption and the number of extractions.
Directly changing a stored element’s priority without notifying or repairing the queue can break heap order. Similarly, if priorities depend on time or other mutable external state, their relative order must remain valid or the structure must be updated.
Applications
Graph search and shortest paths
Dijkstra’s algorithm uses a min-priority queue to select the vertex with the smallest tentative distance. For a graph with vertices and edges, an adjacency-list implementation with an indexed binary heap takes
time. With a Fibonacci heap, the corresponding bound is . These bounds assume nonnegative edge weights, as required by Dijkstra’s algorithm.
A* search prioritizes candidate states using an estimated total path cost, commonly written
where is the known cost to reach a state and estimates the remaining cost.
Priority queues also appear in minimum spanning tree algorithms and other procedures that repeatedly select the currently best candidate.
Scheduling and event processing
In CPU scheduling, ready tasks may be ordered by priority, deadline, or another scheduling key. A priority queue supplies the selection mechanism; it does not by itself define the scheduling policy.
Discrete-event simulations maintain a queue of future events ordered by simulated execution time. The simulator repeatedly extracts the earliest event, processes it, and inserts any newly generated events. Timer management and some event-loop implementations use a similar arrangement.
Strict priority scheduling can cause starvation if higher-priority work continually arrives. Techniques such as priority aging change the scheduling policy to address this; fairness is not an inherent property of a priority queue.
Compression, merging, and selection
Huffman coding repeatedly removes the two lowest-weight nodes and inserts a node representing their combination.
A priority queue can also merge sorted sequences by maintaining the next available element from each sequence. For total elements, this takes time, apart from input and output costs.
To retain the largest elements of a stream, a min-heap of size at most keeps the smallest retained element at its root. Each new candidate can then be rejected or used to replace that root in time.
Relationship to sorting and queues
Repeatedly extracting the minimum from a priority queue produces elements in nondecreasing order. Heapsort exploits heap ordering to achieve worst-case running time.
The comparison-sorting lower bound also constrains priority queues. For arbitrary comparable keys, a queue cannot provide both insertion and extraction in constant amortized time for every input: inserting items and extracting them all would otherwise yield a comparison-based sorting algorithm taking time.
This argument does not apply unchanged to restricted key domains. Small integer priorities can be handled with buckets, while specialized integer queues can exploit the representation of keys or restrictions on their order.
An ordinary queue or a stack can be modeled by assigning priorities based on arrival order. Their specialized implementations are generally simpler and provide stronger operation-specific efficiency.
Practical limitations and interface details
A priority queue guarantees access to an extreme element, not sorted iteration. Traversing a heap’s backing array usually reveals neither insertion order nor priority order.
A standard binary heap also does not support especially efficient melding: concatenating two heap arrays and rebuilding takes time linear in their combined size. Applications that meld frequently may favor a meldable heap.
For concurrent computing, simultaneous insertions and extractions require coordination. Exact minimum extraction can become a contention point because many workers compete for the same end of the ordering. Some concurrent designs relax the requirement and return an element near the minimum, trading strict semantics for greater throughput.
Finally, standard-library interfaces expose different capabilities. A library priority queue may support only insertion, inspection, and extraction even if its underlying structure could support additional operations. Stability, arbitrary deletion, priority updates, thread safety, and empty-queue behavior are properties of the particular interface rather than universal guarantees.