Brodal queue
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
In the following time complexities[3] O(f) is an asymptotic upper bound and Θ(f) is an asymptotically tight bound (see Big O notation). Function names assume a min-heap.
Operation | Binary[3] | Binomial[3] | Fibonacci[3] | Pairing[4] | Brodal[5][lower-alpha 1] | Rank-pairing[7] | Strict Fibonacci[8] |
---|---|---|---|---|---|---|---|
find-min | Θ(1) | Θ(log n) | Θ(1) | Θ(1) | Θ(1) | Θ(1) | Θ(1) |
delete-min | Θ(log n) | Θ(log n) | O(log n)[lower-alpha 2] | O(log n)[lower-alpha 2] | O(log n) | O(log n)[lower-alpha 2] | O(log n) |
insert | O(log n) | Θ(1)[lower-alpha 2] | Θ(1) | Θ(1) | Θ(1) | Θ(1) | Θ(1) |
decrease-key | Θ(log n) | Θ(log n) | Θ(1)[lower-alpha 2] | o(log n)[lower-alpha 2][lower-alpha 3] | Θ(1) | Θ(1)[lower-alpha 2] | Θ(1) |
merge | Θ(n) | O(log n)[lower-alpha 4] | Θ(1) | Θ(1) | Θ(1) | Θ(1) | Θ(1) |
References
- 1 2 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. J. Functional Programming.
- 1 2 3 4 Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. (1990). Introduction to Algorithms (1st ed.). MIT Press and McGraw-Hill. ISBN 0-262-03141-8.
- ↑ Iacono, John (2000), "Improved upper bounds for pairing heaps", Proc. 7th Scandinavian Workshop on Algorithm Theory, Lecture Notes in Computer Science, 1851, Springer-Verlag, pp. 63–77, doi:10.1007/3-540-44985-X_5
- ↑ Brodal, Gerth S. (1996), "Worst-Case Efficient Priority Queues", Proc. 7th Annual ACM-SIAM Symposium on Discrete Algorithms (PDF), pp. 52–58
- ↑ Goodrich, Michael T.; Tamassia, Roberto (2004). "7.3.6. Bottom-Up Heap Construction". Data Structures and Algorithms in Java (3rd ed.). pp. 338–341.
- ↑ Haeupler, Bernhard; Sen, Siddhartha; Tarjan, Robert E. (2009). "Rank-pairing heaps" (PDF). SIAM J. Computing: 1463–1485.
- ↑ Brodal, G. S. L.; Lagogiannis, G.; Tarjan, R. E. (2012). Strict Fibonacci heaps (PDF). Proceedings of the 44th symposium on Theory of Computing - STOC '12. p. 1177. doi:10.1145/2213977.2214082. ISBN 9781450312455.
- ↑ Fredman, Michael Lawrence; Tarjan, Robert E. (1987). "Fibonacci heaps and their uses in improved network optimization algorithms" (PDF). Journal of the Association for Computing Machinery. 34 (3): 596–615. doi:10.1145/28869.28874.
- ↑ Pettie, Seth (2005). "Towards a Final Analysis of Pairing Heaps" (PDF). Max Planck Institut für Informatik.