FACTOID # 20: Statistically, Delaware bears more cost of the US Military than any other state.

 Home Encyclopedia Statistics States A-Z Flags Maps FAQ About

 WHAT'S NEW

SEARCH ALL

Search encyclopedia, statistics and forums:

(* = Graphable)

Encyclopedia > Priority queue

A priority queue is an abstract data type in computer programming, supporting the following three operations: In computing, an abstract data type (ADT) is a specification of a set of data and the set of operations that can be performed on the data. ... Computer programming (often shortened to programming or coding) is the process of writing, testing, and maintaining the source code of computer programs. ...

• add an element to the queue with an associated priority
• remove the element from the queue that has the highest priority, and return it
• (optionally) peek at the element with highest priority without removing it

The simplest way to implement a priority queue data type is to keep an associative array mapping each priority to a list of elements with that priority. If association lists are used to implement the associative array, adding an element takes constant time but removing or peeking at the element of highest priority takes linear (O(n)) time, because we must search all keys for the largest one. If a self-balancing binary search tree is used, all three operations take O(log n) time; this is a popular solution in environments that already provide balanced trees but nothing more sophisticated. The van Emde Boas tree, another associative array data structure, can perform all three operations in O(log log n) time, but at a space cost for small queues of about O(2m/2), where m is the number of bits in the priority value, which may be prohibitive. In mathematics, an element (also called a member) is an object contained in a set (or more generally a class). ... In providing services in computer science, transport, and operations research a queue (pronounced kyew) is a buffer where various entities such as data, objects, persons, or events are stored and waiting to be processed. ... Priority can refer to in telecommunications, the right to occupy a specific frequency for authorized uses, free of harmful interference from stations of other agencies a synonym of priority level in DOD record communications systems, one of the four levels of precedence used to establish the time frame for handling... An associative array (also map, hash, dictionary, finite map, lookup table, and in query-processing an index or index file) is an abstract data type composed of a collection of keys and a collection of values, where each key is associated with one value. ... In computing, a self-balancing binary search tree or height-balanced binary search tree is a binary search tree that attempts to keep its height, or the number of levels of nodes beneath the root, as small as possible at all times, automatically. ... A van Emde Boas tree (or van Emde Boas priority queue), also known as a vEB tree, is a tree data structure which implements an associative array with m-bit integer keys. ...

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 heaps add several more operations, but require O(log n) time for peeking. Fibonacci heaps can insert elements, peek at the maximum priority element, and increase an element's priority in amortized constant time (deletions are still O(log n)). Example of a complete binary max heap 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(A) â‰¥ key(B). ... A binary tree, a simple type of branching linked data structure. ... Example of a complete binary max heap. ... In computer science, a binomial heap is a data structure similar to binary heap but also supporting the operation of merging two heaps quickly. ... In computer science, a Fibonacci heap is a data structure similar to a binomial heap but with a better amortized running time. ... In computational complexity theory, amortized analysis is the time per operation averaged over a worst_case sequence of operations. ...

The Standard Template Library (STL), part of the C++ 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 (it strictly adheres to its abstract data type definition). Java's library contains a `PriorityQueue` class. The Standard Template Library (STL) is a software library included in the C++ Standard Library. ... C++ (pronounced see plus plus, IPA: ) is a general-purpose programming language with high-level and low-level capabilities. ... Year 1998 (MCMXCVIII) was a common year starting on Thursday (link will display full 1998 Gregorian calendar). ... It has been suggested that this article or section be merged with Container (data structure). ... In computer programming, templates are a feature of the C++ programming language that allow code to be written without consideration of the data type with which it will eventually be used. ... In computer science, an iterator is an object which allows a programmer to traverse through all the elements of a collection, regardless of its specific implementation. ...

### 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. This article does not cite any references or sources. ... â€œComputer Networksâ€ redirects here. ... Cisco 1800 Router A router is a device that finds the proper place for megabyte to fly between random watsasfnblksjglawbsj, and forwards data packets to the next device along this path. ... This article needs additional references or sources for verification. ... The Real-time Transport Protocol (or RTP) defines a standardized packet format for delivering audio and video over the Internet. ... An overview of how VoIP works A typical analog telephone adapter for connecting an ordinary phone to a VoIP network Ciscos implementation of VoIP - IP Phone Voice over Internet Protocol, also called VoIP, IP Telephony, Internet telephony, Broadband telephony, Broadband Phone and Voice over Broadband is the routing of...

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 lever control instances such as the Cisco Callmanager, which can be programmed to inhibit calls which would exceed the programmed bandwidth limit. Cisco Systems, Inc. ... CallManager is a Cisco product. ...

### 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. In discrete event simulation, the operation of a system is represented as a chronological sequence of events. ...

See also: Scheduling (computing), queueing theory Scheduling is a key concept in computer multitasking and multiprocessing operating system design, and in real-time operating system design. ... Queueing theory (also commonly spelled queuing theory) is the mathematical study of waiting lines (or queues). ...

### A* search algorithm

The A* search algorithm finds the shortest path between two vertices of a weighted graph, trying out the most promising routes first. The priority queue 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. In computer science, A* (pronounced A star) is a graph/tree search algorithm that finds a path from a given initial node to a given goal node (or one passing a given goal test). ... This article just presents the basic definitions. ... One major problem that has plagued graph theory since its inception is the consistent lack of consistency in terminology. ...

## Implementations

While relying on heapsort is a common way to implement priority queues, for integer data faster implementations exist.

• When the set of keys is {1, 2, ..., C}, a data structure by Emde Boas supports the minimum, maximum, insert, delete, search, extract-min, extract-max, predecessor and successor operations in O(loglogC) time.[1]
• An algorithm by Fredman and Willard implements the minimum operation in O(1) time and insert and extract-min operations in time.[2]

## Relationship to sorting algorithms

The semantics 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 algorithms, once the layer of abstraction provided by the priority queue is removed. This sorting method is equivalent to the following sorting algorithms: In computer science, operational semantics is a way to give meaning to computer programs in a mathematically rigorous way (See formal semantics of programming languages). ... In computer science and mathematics, a sorting algorithm is an algorithm that puts elements of a list in a certain order. ... In computer science, abstraction is a mechanism and practice to reduce and factor out details so that one can focus on a few concepts at a time. ...

• Heapsort if the priority queue is implemented with a heap.
• Selection sort if the priority queue is implemented with an unordered array.
• Insertion sort if the priority queue is implemented with an ordered array.

A run of the heapsort algorithm sorting an array of randomly permuted values. ... Selection sort is a sorting algorithm, specifically an in-place comparison sort. ... Example of insertion sort sorting a list of random numbers. ...

Results from FactBites:

 Priority queue - Wikipedia, the free encyclopedia (444 words) 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. 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.
More results at FactBites »

Share your thoughts, questions and commentary here