Editing Priority queue (section)

== Applications ==

=== Bandwidth management ===

Priority queuing can be used to manage limited resources such as [[Bandwidth (computing)|bandwidth]] on a transmission line from a [[computer network|network]] [[router (computing)|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 [[Real-time Transport Protocol|RTP]] stream of a [[Voice over Internet Protocol|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 line communication|power lines]], phone lines and [[Ethernet over coax|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 Systems, Inc.|Cisco]] [[Callmanager]], which can be programmed to inhibit calls which would exceed the programmed bandwidth limit.
<!-- this was marked IMHO in the original
Priority queues exist on ISO-layer 2 (which is Ethernet or WAN interfaces such as T1 / E1) and are filled by entry-criterions such as [[Diffserv]] Codepoints or IP-Precedence. Network equipment usually can be programmed to pick up priority packets by the layer 4 info (IP protocol and port) or the new one by a mechanism called [[NBAR]].
-->

=== Discrete event simulation ===

Another use of a priority queue is to manage the events in a [[discrete event simulation]]. 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]]

=== 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 algorithm]], although one also needs the ability to alter the priority of a particular vertex in the priority queue efficiently.

If instead, a graph is stored as node objects, and priority-node pairs are inserted into a heap, altering the priority of a particular vertex is not necessary if one tracks visited nodes. Once a node is visited, if it comes up in the heap again (having had a lower priority number associated with it earlier), it is popped-off and ignored.

=== Huffman coding ===

[[Huffman coding]] requires one to repeatedly obtain the two lowest-frequency trees. A priority queue is [[Huffman coding#Compression|one method of doing this]].

=== Best-first search algorithms ===

[[Best-first search]] algorithms, like the [[A* search algorithm]], find the shortest path between two [[vertex (graph theory)|vertices]] or [[Node (graph theory)|nodes]] of a [[weighted graph]], trying out the most promising routes first. A priority queue (also known as the ''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 is given highest priority. If memory limitations make best-first search impractical, variants like the [[SMA*]] algorithm can be used instead, with a [[double-ended priority queue]] to allow removal of low-priority items.

=== ROAM triangulation algorithm ===

The Real-time Optimally Adapting Meshes ([[ROAM]]) 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.

=== Prim's algorithm for minimum spanning tree ===
Using [[Binary heap|min heap priority queue]] in [[Prim's algorithm]] to find the [[minimum spanning tree]] of a [[Connected graph|connected]] and [[undirected graph]], one can achieve a good running time. This min heap priority queue uses the min heap data structure which supports operations such as ''insert'', ''minimum'', ''extract-min'', ''decrease-key''.<ref name="CLR">{{Introduction to Algorithms |edition=3 |pages=634}} "In order to implement Prim's algorithm efficiently, we need a fast way to select a new edge to add to the tree formed by the edges in A."</ref> In this implementation, the [[weighted graph|weight]] of the edges is used to decide the priority of the [[Vertex (graph theory)|vertices]]. Lower the weight, higher the priority and higher the weight, lower the priority.<ref name="GEEKS">
{{cite web
 |url         = http://www.geeksforgeeks.org/greedy-algorithms-set-5-prims-minimum-spanning-tree-mst-2/
 |title       = Prim's Algorithm
 |date = 18 November 2012
 |publisher   = Geek for Geeks
 |access-date  = 12 September 2014
 |url-status     = live
 |archive-url  = https://web.archive.org/web/20140909020508/http://www.geeksforgeeks.org/greedy-algorithms-set-5-prims-minimum-spanning-tree-mst-2/
 |archive-date = 9 September 2014
}}
</ref>