Applications Priority queue

1 applications

1.1 bandwidth management
1.2 discrete event simulation
1.3 dijkstra s algorithm
1.4 huffman coding
1.5 best-first search algorithms
1.6 roam triangulation algorithm
1.7 prim s algorithm minimum spanning tree

applications
bandwidth management

priority queuing can used manage limited resources such bandwidth on transmission line network router. in event of outgoing traffic queuing due insufficient bandwidth, other queues can halted send traffic highest priority queue upon arrival. ensures prioritized traffic (such real-time traffic, e.g. rtp stream of voip connection) forwarded least delay , least likelihood of being rejected due queue reaching maximum capacity. other traffic can handled when highest priority queue empty. approach used send disproportionately more traffic higher priority queues.

many modern protocols local area networks include concept of priority queues @ media access control (mac) sub-layer ensure high-priority applications (such voip or iptv) experience lower latency other applications can served best effort service. examples include ieee 802.11e (an amendment ieee 802.11 provides quality of service) , itu-t g.hn (a standard high-speed local area network using existing home wiring (power lines, phone lines , coaxial cables).

usually limitation (policer) set limit bandwidth traffic highest priority queue can take, in order prevent high priority packets choking off other traffic. limit never reached due high level control instances such cisco callmanager, can programmed inhibit calls exceed programmed bandwidth limit.

discrete event simulation

another use of priority queue manage events in discrete event simulation. events added queue simulation time used priority. execution of simulation proceeds repeatedly pulling top of queue , executing event thereon.

see also: scheduling (computing), queueing theory

dijkstra s algorithm

when graph stored in form of adjacency list or matrix, priority queue can used extract minimum efficiently when implementing dijkstra s algorithm, although 1 needs ability alter priority of particular vertex in priority queue efficiently.

huffman coding

huffman coding requires 1 repeatedly obtain 2 lowest-frequency trees. priority queue 1 method of doing this.

best-first search algorithms

best-first search algorithms, a* search algorithm, find shortest path between 2 vertices or nodes of weighted graph, trying out promising routes first. priority queue (also known fringe) used keep track of unexplored routes; 1 estimate (a lower bound in case of a*) of total path length smallest given highest priority. if memory limitations make best-first search impractical, variants sma* algorithm can used instead, double-ended priority queue allow removal of low-priority items.

roam triangulation algorithm

the real-time optimally adapting meshes (roam) algorithm computes dynamically changing triangulation of terrain. works splitting triangles more detail needed , merging them less detail needed. algorithm assigns each triangle in terrain priority, related error decrease if triangle split. algorithm uses 2 priority queues, 1 triangles can split , triangles can merged. in each step triangle split queue highest priority split, or triangle merge queue lowest priority merged neighbours.

prim s algorithm minimum spanning tree

using min heap priority queue in prim s algorithm find minimum spanning tree of connected , undirected graph, 1 can achieve running time. min heap priority queue uses min heap data structure supports operations such insert, minimum, extract-min, decrease-key. in implementation, weight of edges used decide priority of vertices. lower weight, higher priority , higher weight, lower priority.