Priority queue
In computer science, a priority queue ( also priority list, priority queue, priority queue or priority queue called english ) a particular abstract data structure, more precisely an extended form a queue. The elements that are placed in the queue, a key is given, determining the order of processing of the elements.
Operations
Priority queues have the operations
- Insert, to insert an element and
- ExtractMin, to return and to remove the element with the smallest key ( = highest priority)
Assist.
There are also operations that are particularly important for online algorithms:
- Remove Remove an element
- Decreasekey the key value decrease ( = raise the priority )
Implementation
The implementation of priority queues can be done on AVL trees. Both insert as can also extractMin then in O ( log n) time to run. Another possibility is to use partially ordered trees ( heap ). Again, the time complexity is O ( log n).
Examples of data structures that implement queues priority efficiently are,
- AVL tree
- Binary heap
- Binomial heap
- Fibonacci heap ( amortized running time for remove and extractMin O ( log n ), otherwise O (1), worst case O ( n ) or O (log n) )
- K- Level Buckets
- Links tree
- Radix heap
- Van Emde Boas priority queue
Applications
Priority queuing may be used to implement a discrete event simulation. It can be calculated for specific events as key times, the time - event pair is inserted into the priority queue and the priority queue is then the most current (ie to be processed next ) event.
Greedy algorithms also make use of priority queues, because there is often a minimum or maximum needs to be an amount determined. One of the most well-known algorithms of this type is the Dijkstra algorithm for computing shortest paths.
Extensions
In addition to the classical single-ended priority queue, there are also double-ended. These also support an operation extractMax to extract the element with the largest key. One way to implement such data structures offer Doppelheaps. Alternatively, data structures, such as min-max heaps can be used that directly support double-ended priority queues.