Priority Queues
By Stefan Xenos
| Intuitive Definition |
A priority queue is a data structure that allows the removal of the element with the smallest value. The most common type of priority queue is a heap. A heap is a tree where the child of each node is no smaller than its parent.
|
| Lower Bound |
An implementation based on comparisons requires at least Ω(lg n) average-case time for either insertion or removal. Any priority queue that beats this must make use of some other property, or make assumptions about the input.
|
| Name |
Type |
Ext-Min |
Delete |
Insert |
Decr-Key |
Merge |
Min |
Description |
| Binary heap |
wc |
O(lg n) |
O(lg n) |
O(lg n) |
O(lg n) |
Θ(n) |
O(1) |
Common, simple heap. Efficient unless decrease-key or merge is needed. |
| av |
|
|
O(1) |
|
|
|
| Fibonacci heap
[FT87]
|
am |
O(lg n) |
O(lg n) |
O(1) |
O(1) |
O(1) |
O(1) |
Complex to implement. Efficient average-case merge and decrease-key.
[C]
|
| Trinomial heap |
am |
O(lg n)* |
O(lg n)* |
O(1)* |
O(1)* |
O(1)* |
O(1)* |
Intended as a simpler alternative to relaxed heaps |
| wc |
|
|
|
O(1)* |
|
|
| Binomial heap |
wc |
O(lg n) |
O(lg n) |
O(lg n) |
O(lg n) |
O(lg n) |
O(lg n) |
Offers more efficient merging than binary heaps. |
| Relaxed heap
[DGST88]
|
wc |
O(lg n) |
O(lg n) |
|
O(1) |
|
|
Guarantees O(1) worst case running time for Decrease-Key. |
| am |
|
|
O(1) |
|
O(1) |
O(1) |
|
2-3 heap
[Tad99]
|
am |
O(lg n) |
|
O(1) |
O(1) |
|
O(lg n) |
Intended as a simpler alternative to Fibonacci heaps |
| Skew heap
[ST86]
|
am |
O(lg n) |
|
O(lg n) |
|
O(lg n)* |
|
A heuristically balanced binary heap |
| wc |
O(n) |
|
O(n) |
|
O(n) |
|
| van Emde Boas tree
[BKZ76]
|
wc |
O(lg lg m) |
|
O(lg lg m) |
|
|
O(lg lg m) |
Restricted to integers in the range 0 to m, requires O(m) storage space |
| Sorted linked list |
wc |
O(1) |
O(1) |
O(n) |
O(n) |
O(n) |
O(1) |
Median pointer linked lists are typically used |
| Splay tree
[ST85]
|
am |
|
|
O(lg n) |
|
|
|
A heuristically balanced binary search tree |
| wc |
O(1) |
|
O(n) |
|
|
|
| Calendar queue
[Bro88]
|
av |
O(1) |
|
O(1) |
|
|
|
Uses uniform buckets. O(1) expected performance. |
| wc |
O(n) |
|
O(n) |
|
|
|
| Lazy queue
[Ron93]
|
av |
O(1) |
|
O(1) |
|
|
|
Three partially sorted queues for near, far, and very far events. |
| am |
O(n) |
|
O(n) |
|
|
|
| wc |
O(n lg n) |
|
O(n lg n) |
|
|
|
| Henriksen's data structure
[Hen77]
|
av |
O(1) |
|
O(lg n) |
|
|
|
Uses an array of pointers into a linked list. The array is used for binary searches and the list is used for ordering. |
| am |
O(1) |
|
O(sqrt(n)) |
|
|
|
| wc |
O(1) |
|
O(n) |
|
|
|
| Skip lists
[Pugh90]
|
am |
O(1) |
|
O(lg n) |
|
|
|
Linked list where each node has pointers to several successors. Forms randomly-balanced BST
[C]
|
| wc |
O(1) |
|
O(n) |
|
|
|
| SPEEDESQ
[Ste92]
|
av |
O(1) |
|
O(1) |
|
|
|
Two lists, one sorted (for removal) and one unsorted (for insertion) |
| am |
O(n) |
|
O(1) |
|
|
|
| wc |
O(n lg n) |
|
O(1) |
|
|
|
| Ladder Queue
[WRI05]
|
av |
O(1) |
|
O(1) |
|
|
|
Indended for large-scale simulation event queues |
| n =
|
Number of elements in the heap |
| av |
Expected-case amortized time analysis was used |
| am |
Amortized time analysis was used |
| wc |
Worst-case time analysis was used |
| * |
This time bound has not been verified from a reliable source |
About HeapsHeaps are a type of priority queue. Since many of the original priority queues were implemented as heaps, the terms "heap" and "priority queue" are often used interchangeably. There are differences, however. Technically a heap is a tree which maintains the heap ordering property. That is, the children of each node have values which are not less than their parent. For example, a calendar queue is not a heap, but may be used as a priority queue. Uses for Priority QueuesPriority queues that support O(1) time decrease-key operations are useful for implementing Prim's algorithm and Dijkstra's algorithm. Heaps are often used to implement heap-sort, where a set of elements are sorted by inserting them into a heap and then extracting them one at a time using the extract-min operation. Priority queues can be used to schedule events. An event is scheduled by inserting it into the queue, with its key is set to the time at which the event should happen. An event processor would determine the time of the next event by examining the key of the smallest element in the queue. ResourcesLee Killough's site has a large amount of heap-related material, including many online papers and studies Documentation and C source code for Fibonacci heaps, 2-3 heaps, and trinomial heaps can be found in the Algorithm Repository. Many of the quoted runtimes on this page and several of the references came from a comparative study by
Robert Ronngren
and Rassul Ayani [RA97]
Bibliography
| BKZ76 |
P. van Emde Boas, R. Kaas and E. Zijlstra
"Design and implementation of an efficient priority queue,"
Theory of Computing Systems 10, No. 1, 1976, (99-127).
|
| Bro88 |
Brown, R.
"Calendar queues: A fast O(1) priority queue implementation for the simulation event set problem,"
Communication of the ACM 31, No. 10, 1988, (1220-1227).
|
| DGST88 |
James R. Driscoll, Harold N. Gabow, Ruth Shrairman and Robert E. Tarjan
"Relaxed heaps: An alternative to Fibonacci heaps with applications to parallel computation,"
Communications of the ACM 31, No. 11, 1988, (1343-1354).
|
| FT87 |
Michael L. Fredman and Robert E. Tarjan
"Heaps and their uses in improved network optimization algorithms,"
Journal of the ACM 34, No. 3, 1987, (596-615).
|
| Hen77 |
Henriksen, J. O.
"An improved events list algorithm,"
Proceedings of the 1977 Winter Simulation Conference 1977, (547-557).
|
| Pugh90 |
Pugh, W.
"Skip lists: A probabilistic alternative to balanced trees,"
Communication of the ACM 33, No. 6, 1990, (668-676).
|
| RA97 |
Rönngren, R. and Ayani, R.
"A comparative study of parallel and sequential priority queue algorithms,"
ACM Transactions on Modeling and Computer Simulation (TOMACS) 7, No. 2, 1997, (157-209).
|
| Ron93 |
Rönngren, R., Riboe, J. and Ayani, R.
"Lazy queue: New approach to implementing the pending event set,"
International Journal in Computer Simulation 31993, (303-332).
|
| ST85 |
Sleator, D. D. and Tarjan, R. E.
"Self-adjusting binary search trees,"
Journal of the ACM 32, No. 3, 1985, (652-686).
|
| ST86 |
Sleator, D. D. and Tarjan, R. E.
"Self-adjusting heaps,"
SIAM Journal on Computing 15, No. 1, 1986, (52-69).
|
| Ste92 |
Steinman, J. S.
"SPEEDDES: A unified approach to parallel simulation,"
Proceedings of the Sixth Workshop on Parallel and Distributed Simulation 24, No. 3, 1992, (75-84).
|
| Tad99 |
Tadao Takoka
"Theory of 2-3 Heaps,"
Computing and Combinatorics 1999, (41-50).
|
| WRI05 |
Wai Teng Tang, Rick Mong Goh and Ian Li-Jin
"Ladder queue: An O(1) priority queue structure for large-scale discrete event simulation,"
ACM Transactions on Modeling and Computer Simulation (TOMACS) 15, No. 3, 2005, (175-204).
|
[Sorting] [Priority Queues]
Copyright © 2002, 2003, 2007 Stefan Xenos
|