Priority queue
|
|
A priority queue is an ADT (abstract data type) supporting the following two operations:
- add an element to the queue with an associated priority
- remove the element from the queue that has the highest priority, and return it
The simplest way to implement a priority queue data type is to keep a list of records containing elements and priorities; removing an element requires searching the list sequentially for the element with the highest priority.
This makes removing an element O(n) in the number of elements in the queue, which is inefficient if the queue gets large; the standard implementation is a binary heap (runtime O(log n)), to the extent that the words are occasionally treated as synonyms. Other popular implementations include binomial heaps, fibonacci heaps (asymptotically superior in some cases), balanced binary trees (often used due to their easy availability in the Java standard library), and more general structures such as the van Emde Boas tree.
The Standard Template Library (STL), part of the C++ programming language 1998 standard, specifies "priority_queue" as one of the STL container adaptor class templates. Unlike actual STL containers, it does not allow iteration of its elements.
| Contents |
Applications
Bandwidth Management
Priority queuing can be used to manage limited resources such as bandwidth 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. a 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.
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 higher lever 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 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, queuing theory
External links
- Descriptions (http://leekillough.com/heaps/) by Lee Killough