Brodal queue
Template:Infobox data structureTemplate:Short description In computer science, the Brodal queue is a heap/priority queue structure with very low worst case time bounds: for insertion, find-minimum, meld (merge two queues) and decrease-key and for delete-minimum and general deletion. They are the first heap variant to achieve these bounds without resorting to amortization of operational costs. Brodal queues are named after their inventor Gerth Stølting Brodal.[1]
While having better asymptotic bounds than other priority queue structures, they are, in the words of Brodal himself, "quite complicated" and "[not] applicable in practice."[1] Brodal and Okasaki describe a persistent (purely functional) version of Brodal queues.[2]
Summary of running times
Here are time complexities[3] of various heap data structures. The abbreviation Template:Abbr indicates that the given complexity is amortized, otherwise it is a worst-case complexity. For the meaning of "O(f)" and "Θ(f)" see Big O notation. Names of operations assume a min-heap.
| Operation | find-min | delete-min | decrease-key | insert | meld | make-heapTemplate:Efn |
|---|---|---|---|---|---|---|
| Binary[3] | Θ(1) | Θ(log n) | Θ(log n) | Θ(log n) | Θ(n) | Θ(n) |
| Skew[4] | Θ(1) | O(log n) Template:Abbr | O(log n) Template:Abbr | O(log n) Template:Abbr | O(log n) Template:Abbr | Θ(n) Template:Abbr |
| Leftist[5] | Θ(1) | Θ(log n) | Θ(log n) | Θ(log n) | Θ(log n) | Θ(n) |
| Binomial[3][6] | Θ(1) | Θ(log n) | Θ(log n) | Θ(1) Template:Abbr | Θ(log n)Template:Efn | Θ(n) |
| Skew binomial[7] | Θ(1) | Θ(log n) | Θ(log n) | Θ(1) | Θ(log n)Template:Efn | Θ(n) |
| 2–3 heap[8] | Θ(1) | O(log n) Template:Abbr | Θ(1) | Θ(1) Template:Abbr | O(log n)Template:Efn | Θ(n) |
| Bottom-up skew[4] | Θ(1) | O(log n) Template:Abbr | O(log n) Template:Abbr | Θ(1) Template:Abbr | Θ(1) Template:Abbr | Θ(n) Template:Abbr |
| Pairing[9] | Θ(1) | O(log n) Template:Abbr | o(log n) Template:AbbrTemplate:Efn | Θ(1) | Θ(1) | Θ(n) |
| Rank-pairing[10] | Θ(1) | O(log n) Template:Abbr | Θ(1) Template:Abbr | Θ(1) | Θ(1) | Θ(n) |
| Fibonacci[3][11] | Θ(1) | O(log n) Template:Abbr | Θ(1) Template:Abbr | Θ(1) | Θ(1) | Θ(n) |
| Strict Fibonacci[12]Template:Efn | Θ(1) | Θ(log n) | Θ(1) | Θ(1) | Θ(1) | Θ(n) |
| Brodal[13]Template:Efn | Θ(1) | Θ(log n) | Θ(1) | Θ(1) | Θ(1) | Θ(n)[14] |
Gerth Stølting Brodal
Gerth Stølting Brodal is a professor at the University of Aarhus, Denmark.[15] He is best known for the Brodal queue.
References
- ↑ 1.0 1.1 Gerth Stølting Brodal (1996). Worst-case efficient priority queues. Proc. 7th ACM-SIAM Symposium on Discrete Algorithms, pp. 52–58
- ↑ Gerth Stølting Brodal and Chris Okasaki (1996). Optimal purely functional priority queues. Journal of Functional Programming.
- ↑ 3.0 3.1 3.2 3.3 Template:Introduction to Algorithms
- ↑ 4.0 4.1 Template:Cite journal
- ↑ Template:Cite book
- ↑ Template:Cite web
- ↑ Template:Citation
- ↑ Template:Citation
- ↑ Template:Citation
- ↑ Template:Cite journal
- ↑ Template:Cite journal
- ↑ Template:Cite conference
- ↑ Template:Citation
- ↑ Template:Cite book
- ↑ Template:Cite web