Priority queue
Encyclopedia
A priority queue is an abstract data type
in computer programming
.
It is exactly like a regular queue or stack
data structure, but additionally, each element is associated with a "priority".
It is a common misconception that a priority queue is a heap
. A priority queue is an abstract concept like "a list" or "a map"; just as a list can be implemented with a linked list
or an array, a priority queue can be implemented with a heap or a variety of other methods.
A priority queue must at least support the following operations:
More advanced implementations may support more complicated operations, such as pull_lowest_priority_element, inspecting the first few highest- or lowest-priority elements (peeking at the highest priority element can be made O(1) time in nearly all implementations), clearing the queue, clearing subsets of the queue, performing a batch insert, merging two or more queues into one, incrementing priority of any element, etc.
Stacks and queues may be modeled as particular kinds of priority queues. In a stack, the priority of each inserted element is monotonically increasing; thus, the last element inserted is always the first retrieved. In a queue, the priority of each inserted element is monotonically decreasing; thus, the first element inserted is always the first retrieved.
These implementations are almost always terribly inefficient, but are meant to illustrate the concept of a priority queue.
Note that from a computational-complexity standpoint, priority queues are equivalent to sorting algorithms. See the next section for how efficient sorting algorithms can create efficient priority queues.
as their backbone, giving O(log n)
performance for inserts and removals, and O(n)
to build initially. Alternatively, if a self-balancing binary search tree
is used, insertion and removal also take O(log n)
time, although building the tree from an existing sequence of elements takes O(n log n) time; this is a popular solution where one already has access to these data structures, such as through third-party or standard libraries.
There are a number of specialized heap
data structures that either supply additional operations or outperform the above approaches. The binary heap
uses O(log n) time for both operations, but allows peeking at the element of highest priority without removing it in constant time. Binomial heap
s add several more operations, but require O(log n) time for peeking. Fibonacci heap
s can insert elements, peek at the highest priority element, and increase an element's priority in amortized
constant time (deletions are still O(log n)).
While relying on a heap is a common way to implement priority queues, for integer data faster implementations exist (this can even apply to datatypes that have finite range, such as floats):
For applications that do many "peek" operations for every "extract-min" operation, the time complexity for peek can be reduced to O(1) in all tree and heap implementations by caching the highest priority element after every insertion and removal. (For insertion this adds at most constant cost, since the newly inserted element need only be compared to the previously cached minimum element. For deletion, this at most adds an additional "peek" cost, which is nearly always cheaper than the deletion cost, so overall time complexity is not affected by this change).
of priority queues naturally suggest a sorting method: insert all the elements to be sorted into a priority queue, and sequentially remove them; they will come out in sorted order. This is actually the procedure used by several sorting algorithm
s, once the layer of abstraction
provided by the priority queue is removed. This sorting method is equivalent to the following sorting algorithms:
That is, if there is a sorting algorithm which can sort in O(S) time per key, where S is some function of n and word size , then one can use the given procedure to create a priority queue where pulling the highest-priority element is O(1) time, and inserting new elements (and deleting elements) is O(S) time. For example if one has an O(n lg(lg(n))) sort algorithm, one can easily create a priority queue with O(1) pulling and O(lg(lg(n))) insertion.
".
The Standard Template Library
(STL), and the C++
1998 standard, specifies
s. It implements a max-priority-queue. Unlike actual STL containers, it does not allow iteration
of its elements (it strictly adheres to its abstract data type definition). STL also has utility functions for manipulating another random-access container as a binary max-heap.
Python's heapq module implements a binary min-heap on top of a list.
Java
's library contains a class, which implements a min-priority-queue.
Go
's library contains a container/heap module, which implements a min-heap on top of any compatible data structure.
The Standard PHP Library extension contains the class SplPriorityQueue.
Apple's Core Foundation
framework contains a CFBinaryHeap structure, which implements a min-heap.
on a transmission line from a network
router. In the event of outgoing traffic
queuing due to insufficient bandwidth, all other queues can be halted to send the traffic from the highest priority queue upon arrival. This ensures that the prioritized traffic (such as real-time traffic, e.g. an RTP
stream of a VoIP connection) is forwarded with the least delay and the least likelihood of being rejected due to a queue reaching its maximum capacity. All other traffic can be handled when the highest priority queue is empty. Another approach used is to send disproportionately more traffic from higher priority queues.
Many modern protocols for Local Area Network
s also include the concept of Priority Queues at the Media Access Control
(MAC) sub-layer to ensure that high-priority applications (such as VoIP or IPTV
) experience lower latency than other applications which can be served with Best effort service. Examples include IEEE 802.11e
(an amendment to IEEE 802.11
which provides Quality of Service
) and ITU-T
G.hn
(a standard for high-speed Local area network
using existing home wiring (power lines
, phone lines and coaxial cables
).
Usually a limitation (policer) is set to limit the bandwidth that traffic from the highest priority queue can take, in order to prevent high priority packets from choking off all other traffic. This limit is usually never reached due to high level control instances such as the Cisco Callmanager, which can be programmed to inhibit calls which would exceed the programmed bandwidth limit.
. The events are added to the queue with their simulation time used as the priority. The execution of the simulation proceeds by repeatedly pulling the top of the queue and executing the event thereon.
See also: Scheduling (computing)
, queueing theory
.
or nodes of a weighted graph, trying out the most promising routes first. The priority queue (also known as the fringe) is used to keep track of unexplored routes; the one for which a lower bound on the total path length is smallest is given highest priority. If memory limitations make A* impractical, the SMA* algorithm can be used instead, with a double-ended priority queue
to allow removal of low-priority items.
) algorithm computes a dynamically changing triangulation of a terrain. It works by splitting triangles where more detail is needed and merging them where less detail is needed. The algorithm assigns each triangle in the terrain a priority, usually related to the error decrease if that triangle would be split. The algorithm uses two priority queues, one for triangles that can be split and another for triangles that can be merged. In each step the triangle from the split queue with the highest priority is split, or the triangle from the merge queue with the lowest priority is merged with its neighbours.
Abstract data type
In computing, an abstract data type is a mathematical model for a certain class of data structures that have similar behavior; or for certain data types of one or more programming languages that have similar semantics...
in computer programming
Computer programming
Computer programming is the process of designing, writing, testing, debugging, and maintaining the source code of computer programs. This source code is written in one or more programming languages. The purpose of programming is to create a program that performs specific operations or exhibits a...
.
It is exactly like a regular queue or stack
Stack (data structure)
In computer science, a stack is a last in, first out abstract data type and linear data structure. A stack can have any abstract data type as an element, but is characterized by only three fundamental operations: push, pop and stack top. The push operation adds a new item to the top of the stack,...
data structure, but additionally, each element is associated with a "priority".
- stack: elements are pulled in last-in first-out-order (e.g. a stack of papers)
- queue: elements are pulled in first-in first-out-order (e.g. a line in a cafeteria)
- priority queue: elements are pulled highest-priority-first (e.g. cutting in line, or VIPVIPVIP and V.I.P. is a three-letter acronym that may refer to:-In general:* Vacuum insulated panel* Values, Influence, and Peers, an anti-crime campaign in Ontario elementary schools* Variable Information Printing, a form of on-demand printing...
service).
It is a common misconception that a priority queue is a heap
Heap (data structure)
In computer science, a heap is a specialized tree-based data structure that satisfies the heap property: if B is a child node of A, then key ≥ key. This implies that an element with the greatest key is always in the root node, and so such a heap is sometimes called a max-heap...
. A priority queue is an abstract concept like "a list" or "a map"; just as a list can be implemented with a linked list
Linked list
In computer science, a linked list is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of a datum and a reference to the next node in the sequence; more complex variants add additional links...
or an array, a priority queue can be implemented with a heap or a variety of other methods.
A priority queue must at least support the following operations:
-
insert_with_priority: add an element to the queue with an associated priorityPriorityPriority may refer to:* Priority date, a concept of establishing waiting times in the immigration process by United States Department of State* Priority level, the priority of emergency communications... -
pull_highest_priority_element: remove the element from the queue that has the highest priority, and return it (also known as "pop_element(Off)", "get_maximum_element", or "get_front(most)_element"; some conventions consider lower priorities to be higher, so this may also be known as "get_minimum_element", and is often referred to as "get-min" in the literature; the literature also sometimes implement separate "peek_at_highest_priority_element" and "delete_element" functions, which can be combined to produce "pull_highest_priority_element")
More advanced implementations may support more complicated operations, such as pull_lowest_priority_element, inspecting the first few highest- or lowest-priority elements (peeking at the highest priority element can be made O(1) time in nearly all implementations), clearing the queue, clearing subsets of the queue, performing a batch insert, merging two or more queues into one, incrementing priority of any element, etc.
Similarity to queues
One can imagine a priority queue as a modified queue, but when one would get the next element off the queue, the highest-priority element is retrieved first.Stacks and queues may be modeled as particular kinds of priority queues. In a stack, the priority of each inserted element is monotonically increasing; thus, the last element inserted is always the first retrieved. In a queue, the priority of each inserted element is monotonically decreasing; thus, the first element inserted is always the first retrieved.
Naive implementations
There are a variety of simple, usually inefficient, ways to implement a priority queue. They provide an analogy to help one understand what a priority queue is:- Unsorted implementation: This is perhaps the most naive implementation. Keep all the elements unsorted. Whenever the highest-priority element is requested, search through all elements for the one with the highest priority. (O(1)Big O notationIn mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...
insertion time, O(n)Big O notationIn mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...
pull time due to search)
- Sorted list implementation: Like a checkout line at the supermarket, but where important people get to "cut" in front of less important people. (if using a basic array, this takes O(n)Big O notationIn mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...
insertion time, O(1)Big O notationIn mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...
pullNext time (from the front), and on average O(n*log(n))Big O notationIn mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...
time to initialize (if using quicksort))
These implementations are almost always terribly inefficient, but are meant to illustrate the concept of a priority queue.
Note that from a computational-complexity standpoint, priority queues are equivalent to sorting algorithms. See the next section for how efficient sorting algorithms can create efficient priority queues.
Usual implementation
To get better performance, priority queues typically use a heapHeap (data structure)
In computer science, a heap is a specialized tree-based data structure that satisfies the heap property: if B is a child node of A, then key ≥ key. This implies that an element with the greatest key is always in the root node, and so such a heap is sometimes called a max-heap...
as their backbone, giving O(log n)
Big O notation
In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...
performance for inserts and removals, and O(n)
Big O notation
In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...
to build initially. Alternatively, if a self-balancing binary search tree
Self-balancing binary search tree
In computer science, a self-balancing binary search tree is any node based binary search tree that automatically keeps its height small in the face of arbitrary item insertions and deletions....
is used, insertion and removal also take O(log n)
Big O notation
In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...
time, although building the tree from an existing sequence of elements takes O(n log n) time; this is a popular solution where one already has access to these data structures, such as through third-party or standard libraries.
Effect of different data structures
The designer of the priority queue should take into account what sort of access pattern the priority queue will be subject to, and what computational resources are most important to the designer. The designer can then use various specialized types of heaps:There are a number of specialized heap
Heap (data structure)
In computer science, a heap is a specialized tree-based data structure that satisfies the heap property: if B is a child node of A, then key ≥ key. This implies that an element with the greatest key is always in the root node, and so such a heap is sometimes called a max-heap...
data structures that either supply additional operations or outperform the above approaches. The binary heap
Binary heap
A binary heap is a heap data structure created using a binary tree. It can be seen as a binary tree with two additional constraints:*The shape property: the tree is a complete binary tree; that is, all levels of the tree, except possibly the last one are fully filled, and, if the last level of...
uses O(log n) time for both operations, but allows peeking at the element of highest priority without removing it in constant time. Binomial heap
Binomial heap
In computer science, a binomial heap is a heap similar to a binary heap but also supports quickly merging two heaps. This is achieved by using a special tree structure...
s add several more operations, but require O(log n) time for peeking. Fibonacci heap
Fibonacci heap
In computer science, a Fibonacci heap is a heap data structure consisting of a collection of trees. It has a better amortized running time than a binomial heap. Fibonacci heaps were developed by Michael L. Fredman and Robert E. Tarjan in 1984 and first published in a scientific journal in 1987...
s can insert elements, peek at the highest priority element, and increase an element's priority in amortized
Amortized analysis
In computer science, amortized analysis is a method of analyzing algorithms that considers the entire sequence of operations of the program. It allows for the establishment of a worst-case bound for the performance of an algorithm irrespective of the inputs by looking at all of the operations...
constant time (deletions are still O(log n)).
While relying on a heap is a common way to implement priority queues, for integer data faster implementations exist (this can even apply to datatypes that have finite range, such as floats):
- When the set of keys is {1, 2, ..., C}, a van Emde Boas treeVan Emde Boas treeA van Emde Boas tree , also known as a vEB tree, is a tree data structure which implements an associative array with m-bit integer keys. It performs all operations in O time...
supports the minimum, maximum, insert, delete, search, extract-min, extract-max, predecessor and successor operations in
time, but has a space cost for small queues of about O(2m/2), where m is the number of bits in the priority value. - The Fusion treeFusion treeA fusion tree is a type of tree data structure in computer science. It implements an associative array with integer keys up to a fixed size; by exploiting the constant-time machine word multiplication operation available on many real processors, it is able to achieve all operations inO\lefttime ,...
algorithm by FredmanMichael FredmanMichael Lawrence Fredman is a professor at the Computer Science Department at Rutgers University, United States. He got his Ph. D. degree from Stanford University in 1972 under the supervision of Donald Knuth. He was a member of the mathematics department at the Massachusetts Institute of...
and Willard implements the minimum operation in O(1) time and insert and extract-min operations in
time.
For applications that do many "peek" operations for every "extract-min" operation, the time complexity for peek can be reduced to O(1) in all tree and heap implementations by caching the highest priority element after every insertion and removal. (For insertion this adds at most constant cost, since the newly inserted element need only be compared to the previously cached minimum element. For deletion, this at most adds an additional "peek" cost, which is nearly always cheaper than the deletion cost, so overall time complexity is not affected by this change).
Using a priority queue to sort
The semanticsOperational semantics
In computer science, operational semantics is a way to give meaning to computer programs in a mathematically rigorous way. Operational semantics are classified into two categories: structural operational semantics formally describe how the individual steps of a computation take place in a...
of priority queues naturally suggest a sorting method: insert all the elements to be sorted into a priority queue, and sequentially remove them; they will come out in sorted order. This is actually the procedure used by several sorting algorithm
Sorting algorithm
In computer science, a sorting algorithm is an algorithm that puts elements of a list in a certain order. The most-used orders are numerical order and lexicographical order...
s, once the layer of abstraction
Abstraction (computer science)
In computer science, abstraction is the process by which data and programs are defined with a representation similar to its pictorial meaning as rooted in the more complex realm of human life and language with their higher need of summarization and categorization , while hiding away the...
provided by the priority queue is removed. This sorting method is equivalent to the following sorting algorithms:
- HeapsortHeapsortHeapsort is a comparison-based sorting algorithm to create a sorted array , and is part of the selection sort family. Although somewhat slower in practice on most machines than a well implemented quicksort, it has the advantage of a more favorable worst-case O runtime...
if the priority queue is implemented with a heap. - SmoothsortSmoothsortSmoothsort is a comparison-based sorting algorithm. It is a variation of heapsort developed by Edsger Dijkstra in 1981. Like heapsort, smoothsort's upper bound is O...
if the priority queue is implemented with a Leonardo heap. - Selection sortSelection sortSelection sort is a sorting algorithm, specifically an in-place comparison sort. It has O time complexity, making it inefficient on large lists, and generally performs worse than the similar insertion sort...
if the priority queue is implemented with an unordered array. - Insertion sortInsertion sortInsertion sort is a simple sorting algorithm: a comparison sort in which the sorted array is built one entry at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort...
if the priority queue is implemented with an ordered array. - Tree sortTree sortA tree sort is a sort algorithm that builds a binary search tree from the keys to be sorted, and then traverses the tree so that the keys come out in sorted order. Its typical use is when sorting the elements of a stream from a file...
if the priority queue is implemented with a self-balancing binary search treeSelf-balancing binary search treeIn computer science, a self-balancing binary search tree is any node based binary search tree that automatically keeps its height small in the face of arbitrary item insertions and deletions....
.
Using a sorting algorithm to make a priority queue
A sorting algorithm can also be used to implement a priority queue. Specifically, Thorup says:
We present a general deterministic linear space reduction from priority queues to sorting implying that if we can sort up to n keys in S(n) time per key, then there is a priority queue supporting delete and insert in O(S(n)) time and find-min in constant time.
That is, if there is a sorting algorithm which can sort in O(S) time per key, where S is some function of n and word size , then one can use the given procedure to create a priority queue where pulling the highest-priority element is O(1) time, and inserting new elements (and deleting elements) is O(S) time. For example if one has an O(n lg(lg(n))) sort algorithm, one can easily create a priority queue with O(1) pulling and O(lg(lg(n))) insertion.
Libraries
A priority queue is often considered to be a "container data structureContainer (data structure)
In computer science, a container is a class, a data structure, or an abstract data type whose instances are collections of other objects. In other words; they are used for storing objects in an organized way following specific access rules...
".
The Standard Template Library
Standard Template Library
The Standard Template Library is a C++ software library which later evolved into the C++ Standard Library. It provides four components called algorithms, containers, functors, and iterators. More specifically, the C++ Standard Library is based on the STL published by SGI. Both include some...
(STL), and the C++
C++
C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as an intermediate-level language, as it comprises a combination of both high-level and low-level language features. It was developed by Bjarne Stroustrup starting in 1979 at Bell...
1998 standard, specifies
priority_queue as one of the STL container adaptor class templateTemplate (programming)
Templates are a feature of the C++ programming language that allow functions and classes to operate with generic types. This allows a function or class to work on many different data types without being rewritten for each one....
s. It implements a max-priority-queue. Unlike actual STL containers, it does not allow iteration
Iterator
In computer programming, an iterator is an object that enables a programmer to traverse a container. Various types of iterators are often provided via a container's interface...
of its elements (it strictly adheres to its abstract data type definition). STL also has utility functions for manipulating another random-access container as a binary max-heap.
Python's heapq module implements a binary min-heap on top of a list.
Java
Java (programming language)
Java is a programming language originally developed by James Gosling at Sun Microsystems and released in 1995 as a core component of Sun Microsystems' Java platform. The language derives much of its syntax from C and C++ but has a simpler object model and fewer low-level facilities...
's library contains a class, which implements a min-priority-queue.
Go
Go (programming language)
Go is a compiled, garbage-collected, concurrent programming language developed by Google Inc.The initial design of Go was started in September 2007 by Robert Griesemer, Rob Pike, and Ken Thompson. Go was officially announced in November 2009. In May 2010, Rob Pike publicly stated that Go was being...
's library contains a container/heap module, which implements a min-heap on top of any compatible data structure.
The Standard PHP Library extension contains the class SplPriorityQueue.
Apple's Core Foundation
Core Foundation
Core Foundation is a C application programming interface in Mac OS X & iOS, and is a mix of low-level routines and wrapper functions...
framework contains a CFBinaryHeap structure, which implements a min-heap.
Bandwidth management
Priority queuing can be used to manage limited resources such as bandwidthBandwidth (computing)
In computer networking and computer science, bandwidth, network bandwidth, data bandwidth, or digital bandwidth is a measure of available or consumed data communication resources expressed in bits/second or multiples of it .Note that in textbooks on wireless communications, modem data transmission,...
on a transmission line from a network
Computer network
A computer network, often simply referred to as a network, is a collection of hardware components and computers interconnected by communication channels that allow sharing of resources and information....
router. In the event of outgoing traffic
Traffic
Traffic on roads may consist of pedestrians, ridden or herded animals, vehicles, streetcars and other conveyances, either singly or together, while using the public way for purposes of travel...
queuing due to insufficient bandwidth, all other queues can be halted to send the traffic from the highest priority queue upon arrival. This ensures that the prioritized traffic (such as real-time traffic, e.g. an RTP
Real-time Transport Protocol
The Real-time Transport Protocol defines a standardized packet format for delivering audio and video over IP networks. RTP is used extensively in communication and entertainment systems that involve streaming media, such as telephony, video teleconference applications, television services and...
stream of a VoIP connection) is forwarded with the least delay and the least likelihood of being rejected due to a queue reaching its maximum capacity. All other traffic can be handled when the highest priority queue is empty. Another approach used is to send disproportionately more traffic from higher priority queues.
Many modern protocols for Local Area Network
Local area network
A local area network is a computer network that interconnects computers in a limited area such as a home, school, computer laboratory, or office building...
s also include the concept of Priority Queues at the Media Access Control
Media Access Control
The media access control data communication protocol sub-layer, also known as the medium access control, is a sublayer of the data link layer specified in the seven-layer OSI model , and in the four-layer TCP/IP model...
(MAC) sub-layer to ensure that high-priority applications (such as VoIP or IPTV
IPTV
Internet Protocol television is a system through which television services are delivered using the Internet protocol suite over a packet-switched network such as the Internet, instead of being delivered through traditional terrestrial, satellite signal, and cable television formats.IPTV services...
) experience lower latency than other applications which can be served with Best effort service. Examples include IEEE 802.11e
IEEE 802.11e
IEEE 802.11e-2005 or 802.11e is an approved amendment to the IEEE 802.11 standard that defines a set of Quality of Service enhancements for wireless LAN applications through modifications to the Media Access Control layer. The standard is considered of critical importance for delay-sensitive...
(an amendment to IEEE 802.11
IEEE 802.11
IEEE 802.11 is a set of standards for implementing wireless local area network computer communication in the 2.4, 3.6 and 5 GHz frequency bands. They are created and maintained by the IEEE LAN/MAN Standards Committee . The base version of the standard IEEE 802.11-2007 has had subsequent...
which provides Quality of Service
Quality of service
The quality of service refers to several related aspects of telephony and computer networks that allow the transport of traffic with special requirements...
) and ITU-T
ITU-T
The ITU Telecommunication Standardization Sector is one of the three sectors of the International Telecommunication Union ; it coordinates standards for telecommunications....
G.hn
G.hn
G.hn is the common name for a home network technology family of standards developed under the International Telecommunication Union's Standardization arm and promoted by the HomeGrid Forum...
(a standard for high-speed Local area network
Local area network
A local area network is a computer network that interconnects computers in a limited area such as a home, school, computer laboratory, or office building...
using existing home wiring (power lines
Power line communication
Power line communication or power line carrier , also known as power line digital subscriber line , mains communication, power line telecom , power line networking , or broadband over power lines are systems for carrying data on a conductor also used for electric power transmission.A wide range...
, phone lines and coaxial cables
Ethernet over coax
Ethernet over Coax is a family of technologies that supports the transmission of Ethernet frames over coaxial cable.- History :The first Ethernet standard, known as 10BASE5 in the family of IEEE 802.3, specified baseband operation over coaxial cable...
).
Usually a limitation (policer) is set to limit the bandwidth that traffic from the highest priority queue can take, in order to prevent high priority packets from choking off all other traffic. This limit is usually never reached due to high level control instances such as the Cisco Callmanager, which can be programmed to inhibit calls which would exceed the programmed bandwidth limit.
Discrete event simulation
Another use of a priority queue is to manage the events in a discrete event simulationDiscrete Event Simulation
In discrete-event simulation, the operation of a system is represented as a chronological sequence of events. Each event occurs at an instant in time and marks a change of state in the system...
. The events are added to the queue with their simulation time used as the priority. The execution of the simulation proceeds by repeatedly pulling the top of the queue and executing the event thereon.
See also: Scheduling (computing)
Scheduling (computing)
In computer science, a scheduling is the method by which threads, processes or data flows are given access to system resources . This is usually done to load balance a system effectively or achieve a target quality of service...
, queueing theory
Queueing theory
Queueing theory is the mathematical study of waiting lines, or queues. The theory enables mathematical analysis of several related processes, including arriving at the queue, waiting in the queue , and being served at the front of the queue...
Dijkstra's algorithm
When the graph is stored in the form of adjacency list or matrix, priority queue can be used to extract minimum efficiently when implementing Dijkstra's algorithmDijkstra's algorithm
Dijkstra's algorithm, conceived by Dutch computer scientist Edsger Dijkstra in 1956 and published in 1959, is a graph search algorithm that solves the single-source shortest path problem for a graph with nonnegative edge path costs, producing a shortest path tree...
.
A* and SMA* search algorithms
The A* search algorithm finds the shortest path between two verticesVertex (graph theory)
In graph theory, a vertex or node is the fundamental unit out of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges , while a directed graph consists of a set of vertices and a set of arcs...
or nodes of a weighted graph, trying out the most promising routes first. The priority queue (also known as the fringe) is used to keep track of unexplored routes; the one for which a lower bound on the total path length is smallest is given highest priority. If memory limitations make A* impractical, the SMA* algorithm can be used instead, with a double-ended priority queue
Double-ended priority queue
A double-ended priority queue is an abstract data type similar to a priority queue except that it allows for efficient removal of both the maximum and minimum element. It is a data structure in which one can insert elements and then remove the elements with minimum or maximum priority. Every...
to allow removal of low-priority items.
ROAM triangulation algorithm
The Real-time Optimally Adapting Meshes (ROAMROAM
Real-time optimally adapting mesh , is a continuous level of detail algorithm that optimizes terrain meshes. On modern computers, sometimes it is more effective to send a small amount of unneeded polygons to the GPU, rather than burden the CPU with LOD calculations—making algorithms like...
) algorithm computes a dynamically changing triangulation of a terrain. It works by splitting triangles where more detail is needed and merging them where less detail is needed. The algorithm assigns each triangle in the terrain a priority, usually related to the error decrease if that triangle would be split. The algorithm uses two priority queues, one for triangles that can be split and another for triangles that can be merged. In each step the triangle from the split queue with the highest priority is split, or the triangle from the merge queue with the lowest priority is merged with its neighbours.
See also
- Batch queueBatch queueA batch queue, sometimes also known as job queue, is a system software data structuremaintained by job scheduler software.Users submit their programs that they want executed, "jobs", to the queue for batch processing....
- ClosureClosure (computer science)In computer science, a closure is a function together with a referencing environment for the non-local variables of that function. A closure allows a function to access variables outside its typical scope. Such a function is said to be "closed over" its free variables...
- Command patternCommand patternIn object-oriented programming, the command pattern is a design pattern in which an object is used to represent and encapsulate all the information needed to call a method at a later time...
- Command queueCommand queueA command queue is a queue for delaying the execution of commands, usually either in order of priority or on a first-in first-out basis. They are often useful in synchronous applications, where a command executor may receive a new command while it is still performing a previous one, and so requires...
- Function objectFunction objectA function object, also called a functor, functional, or functionoid, is a computer programming construct allowing an object to be invoked or called as though it were an ordinary function, usually with the same syntax.-Description:...
- Job schedulerJob schedulerA job scheduler is a software application that is in charge of unattended background executions, commonly known for historical reasons as batch processing....
- Model-view-controllerModel-view-controllerModel–view–controller is a software architecture, currently considered an architectural pattern used in software engineering. The pattern isolates "domain logic" from the user interface , permitting independent development, testing and maintenance of each .Model View Controller...
Further reading
- Thomas H. CormenThomas H. CormenThomas H. Cormen is the co-author of Introduction to Algorithms, along with Charles Leiserson, Ron Rivest, and Cliff Stein. He is a Full Professor of computer science at Dartmouth College and currently Chair of the Dartmouth College Department of Computer Science. Between 2004 and 2008 he directed...
, Charles E. LeisersonCharles E. LeisersonCharles Eric Leiserson is a computer scientist, specializing in the theory of parallel computing and distributed computing, and particularly practical applications thereof; as part of this effort, he developed the Cilk multithreaded language...
, Ronald L. Rivest, and Clifford SteinClifford SteinClifford Stein, a computer scientist, is currently a professor of industrial engineering and operations research at Columbia University in New York, NY, where he also holds an appointment in the Department of Computer Science. Stein is chair of the Industrial Engineering and Operations Research...
. Introduction to AlgorithmsIntroduction to AlgorithmsIntroduction to Algorithms is a book by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. It is used as the textbook for algorithms courses at many universities. It is also one of the most commonly cited references for algorithms in published papers, with over 4600...
, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 6.5: Priority queues, pp.138–142.
External links
- C++ reference for
std::priority_queue - Descriptions by Lee KilloughLee Killough (programmer)Lee Killough is an American programmer who has contributed to the development of source ports for the computer game Doom. He was part of the Boom team and is the author of Marine's Best Friend....
- PQlib - Open source Priority Queue library for C
- libpqueue is a generic priority queue (heap) implementation (in C) used by the Apache HTTP Server project.
- Survey of known priority queue structures by Stefan Xenos
- UC Berkeley - Computer Science 61B - Lecture 24: Priority Queues (video) - introduction to priority queues using binary heap
- Double-Ended Priority Queues by Sartaj SahniSartaj SahniProf. Sartaj Kumar Sahni is an Indian computer scientist, now based in the USA, and is one of the pioneers in the field of data structures. He is a distinguished professor in the Department of Computer and Information Science and Engineering at the University of Florida.- Biography :Sahni received...