Brodal queue
From Wikipedia, the free encyclopedia
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 with these bounds. 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 (functional) version of Brodal queues.[2]
References[edit]
- ^ a b 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.
 |
This algorithms or data structures-related article is a stub. You can help Wikipedia by expanding it. |
