Lecture
A priority queue — is an abstract data type in programming that supports two mandatory operations — add an element and extract the maximum (minimum). It is assumed that a priority can be computed for each element — a real number, or more generally, an element of a linearly ordered set.
The main methods implemented by a priority queue are the following:
Here a smaller key value corresponds to a higher priority.
In some cases it is more natural for the key to grow together with the priority. Then the second method can be called extract_maximum().
There are a number of implementations in which both main operations run, in the worst case, within a time bounded by O(logn) (see «big O» and «little o»), where n — is the number of stored pairs.
A priority queue must support at least the following operations:
This is also known as « pop_element(Off) », « get_maximum_element » or « get_front(most)_element ».
Some conventions reverse the priority order, treating lower values as higher priority, so this may also be known as « get_minimum_element », and in the literature it is often referred to as « get-min.
Instead, this can be specified as separate functions « peek_at_highest_priority_element » and « delete_element », which can be combined to obtain « pull_highest_priority_element ».
In addition, peek (often called find-max or find-min in this context), which returns the element with the highest priority without modifying the queue, is very often implemented and almost always runs in O(1) time. This operation and its O(1) performance are critical for many priority queue applications.
More advanced implementations can support more complex operations, such as pull_lowest_priority_element, inspecting the first few elements with the highest or lowest priority, clearing the queue, clearing subsets of the queue, performing batch insertion, merging two or more queues into one, increasing the priority of any element, and so on.
Stacks and queues can be implemented as special kinds of priority queues, where the priority is determined by the order in which the elements are inserted. In a stack, the priority of each inserted element monotonically increases; thus, the last inserted element is always extracted first. In a queue, the priority of each inserted element monotonically decreases; thus, the first inserted element is always extracted first.
As an example of a priority queue, one can consider a worker's task list. When they finish one task, they move on to the next one — the highest priority one (the key would be the value inverse to the priority) — that is, they perform the extract-maximum operation. The boss adds tasks to the list, specifying their priority, that is, performs the add-element operation.
In practice, the priority queue interface is often extended with other operations:
In indexed priority queues (addressable), it is possible to access elements by index. Such queues can be used, for example, for merging several sorted sequences (multiway merge).
One can also consider double-ended priority queues (DEPQ), which have operations for accessing both the minimum and the maximum element.
A priority queue can be implemented based on various data structures.
The simplest (and not very efficient) implementations can use an unordered or ordered array, or a linked list, suitable for small queues. Here the computations can be either «lazy» (the weight of the computation is shifted onto element extraction) or eager, when inserting an element is more expensive than extracting it. That is, one of the operations can be performed in O(1) time, while the other — in the worst case in O(N), where N — is the length of the queue.
Heap-based implementations are more efficient, where both operations can be performed in the worst case in O(logN) time. These include the binary heap, binomial heap, Fibonacci heap, pairing heap.
The abstract data type (ADT) for a priority queue is obtained from the heap ADT by renaming the corresponding functions. The minimum (maximum) value is always located at the top of the heap.
The Python standard library contains the heap module, which implements a priority queue:
# import two queue functions under the names used in this article from heapq import heappush as insert, heappop as extract_maximum pq = [] # initialize the list insert(pq, (4, 0, "p")) # insert element "p" into the queue with index 0 and priority 4 insert(pq, (2, 1, "e")) insert(pq, (3, 2, "a")) insert(pq, (1, 3, "h")) # print four elements in increasing order of priority print(extract_maximum(pq)[-1] + extract_maximum(pq)[-1] + extract_maximum(pq)[-1] + extract_maximum(pq)[-1])
This example will print the word «heap».
A priority queue can be used to manage limited resources, such as bandwidth on a transmission line from a network router. If an outgoing traffic queue arises due to insufficient bandwidth, all other queues can be halted so that traffic from the highest-priority queue is sent upon arrival. This guarantees that priority traffic (such as real-time traffic, for example an RTP stream from a VoIP connection) will be forwarded with the lowest latency and the lowest probability of being dropped due to the queue reaching maximum capacity. All other traffic can be processed when the highest-priority queue is empty. Another approach used is to send a disproportionately larger amount of traffic from the higher-priority queues.
Many modern local area network protocols also include the concept of priority queues at the media access control (MAC) sublayer, to ensure that high-priority applications (such as VoIP or IPTV) experience less latency than other applications that can be served on a best-effort basis. Examples include IEEE 802.11e (an amendment to IEEE 802.11 that provides quality of service) and ITU-T G.hn (a standard for high-speed local area networking using existing home wiring (power lines, telephone lines, and coaxial cables).
Typically a limit (policer) is set to restrict the bandwidth that traffic from the highest-priority queue can occupy, to prevent high-priority packets from crowding out all other traffic. This limit is usually never reached, because of high-level control instances such as Cisco Callmanager, which can be programmed to block calls that could exceed the programmed bandwidth limit.
Another application of a priority queue is managing events in discrete event simulation. Events are added to the queue, and their simulated time is used as the priority. Running the simulation involves repeatedly pulling the top of the queue and executing the event at that position.
See: Scheduling (computing), queueing theory
If a graph is stored as an adjacency list or matrix, a priority queue can be used for efficient minimum extraction when implementing Dijkstra's algorithm, although the ability to efficiently change the priority of a particular vertex in the priority queue is also required.
If instead the graph is stored as node objects, and priority-node pairs are inserted into a heap, changing the priority of a particular vertex is not required if visited nodes are tracked. After a node has been visited, if it appears again in the heap (having a previously associated lower priority number), it is popped and ignored.
Huffman coding requires repeatedly obtaining the two trees with the lowest frequency. A priority queue is one method for doing this.
Best-first search algorithms, such as the A* search algorithm, find the shortest path between two vertices or nodes of a weighted graph by trying the most promising routes first. A priority queue (also known as a fringe) is used to keep track of unexplored routes; the one for which the estimate (a lower bound in the case of A*) of the total path length is smallest gets the highest priority. If memory constraints make best-first search impractical, variants such as the SMA* algorithm can be used instead, with a double-ended priority queue, to allow low-priority elements to be removed.
The Real-time Optimally Adapting Meshes (ROAM) algorithm computes a dynamically changing triangulation of terrain. It works by splitting triangles where more detail is needed, and merging them where less detail is needed. The algorithm assigns each triangle on the terrain a priority, usually related to the reduction in error if that triangle were split. The algorithm uses two priority queues, one for triangles that can be split, and another for triangles that can be merged. At 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 neighbors.
Using a min-heap priority queue in Prim's algorithm for finding the minimum spanning tree of a connected, undirected graph can achieve good running time. This min-heap priority queue uses a min-heap data structure that supports operations such as insert, minimum, extract minimum, decrease key. In this implementation, the weight of the edges is used to determine the priority of the vertices. The smaller the weight, the higher the priority, and the larger the weight, the lower the priority.
Parallelization can be used to speed up priority queues, but it requires some changes to the priority queue interface. The reason for such changes is that a sequential update usually has only 
or 
cost, and there is no practical benefit from parallelizing such an operation. One possible change is to allow simultaneous access by several processors to the same priority queue. A second possible change is to allow batch operations that operate on k elements rather than just one element. For example, extractMin would remove the first k elements with the highest priority.
If a priority queue allows parallel access, several processes can perform operations in parallel on that priority queue. However, this raises two problems. First, defining the semantics of individual operations is no longer obvious. For example, if two processes want to extract the element with the highest priority, should they get the same element or different ones? This limits the parallelism at the level of the program that uses the priority queue. In addition, since several processes have access to the same element, this leads to contention.
Node 3 is inserted and sets node 2's pointer to node 3. Immediately after this, node 2 is removed, and node 1's pointer is set to node 4. Now node 3 is no longer reachable.
Parallel access to a priority queue can be implemented on the Concurrent Read, Concurrent Write (CRCW) PRAM model. Further, the priority queue is implemented as a skip list. In addition, the CAS atomic synchronization primitive is used to make the skip list lock-free. The nodes of the skip list consist of a unique key, a priority, an array of pointers for each level to the following nodes, and a deletion mark. A deletion mark indicates that the node is about to be deleted by a process. This ensures that other processes can respond appropriately to the deletion.
If concurrent access to the priority queue is allowed, conflicts may arise between two processes. For example, a conflict occurs if one process tries to insert a new node while another process is at the same time about to delete a predecessor of that node. There is a risk that the new node will be added to the skip list but will no longer be accessible. ( See figure )
In shared memory settings, a parallel priority queue can be easily implemented using parallel binary search trees and union-based tree algorithms. In particular, k_extract-min corresponds to a split on a binary search tree, which has cost and yields a tree that contains k the smallest elements. k_insert can be applied by joining the original priority queue and the batch of insertions. If the batch is already sorted by key, k_insert has 
cost. Otherwise, we first need to sort the batch, so the cost will be 
. Other operations for the priority queue can be applied similarly. For example, k_decrease-key can be performed by first applying split, and then join, which first removes the elements and then inserts them back with updated keys. All these operations are highly parallel, and their theoretical and practical efficiency can be found in the relevant research papers.
The rest of this section is devoted to a queue-based algorithm in distributed memory. We assume that each processor has its own local memory and a local (sequential) priority queue. The elements of the global (parallel) priority queue are distributed across all processors.
k_extract-min is performed on a priority queue with three processors. Green elements are returned and removed from the priority queue.
The k_insert operation assigns elements uniformly at random to processors, which insert the elements into their local queues. Note that individual elements can still be inserted into the queue. Using this strategy, the global smallest elements are, with high probability, contained in the union of the local smallest elements of each processor. Thus, each processor holds a representative part of the global priority queue.
This property is used when performing k_extract-min, as the smallest m elements of each local queue are removed and collected into a result set. The elements in the result set are still associated with their original processor. The number of elements m that is removed from each local queue depends on k and the number of processors p . Parallel selection determines the smallest k elements of the result set. With high probability these are the global k smallest elements. If not, m elements are again removed from each local queue and placed into the result set. This is done until the global k smallest elements are in the result set. Now these k elements can be returned. All remaining elements of the result set are inserted back into their local queues. The expected running time of k_extract-min is 
, where 
and n is the size of the priority queue.
The priority queue can be further improved by not moving the remaining elements of the result set directly back to the local queues after the k_extract-min operation. This saves moving elements back and forth all the time between the result set and the local queues.
By removing several elements at once, significant speedup can be achieved. But not all algorithms can use this type of priority queue. For example, Dijkstra's algorithm cannot work on multiple nodes at the same time. The algorithm takes the node with the smallest distance from the priority queue and computes new distances for all its neighboring nodes. If you removed k nodes while working on a single node, you could change the distance to another node among the k nodes. Thus, using k-element operations breaks the label-setting property of Dijkstra's algorithm.
Comments