In
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
, the Brodal queue is a
heap/
priority queue
In computer science, a priority queue is an abstract data-type similar to a regular queue or stack data structure in which each element additionally has a ''priority'' associated with it. In a priority queue, an element with high priority is se ...
structure with very low
worst case
In computer science, best, worst, and average cases of a given algorithm express what the resource usage is ''at least'', ''at most'' and ''on average'', respectively. Usually the resource being considered is running time, i.e. time complexity, b ...
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.
[Gerth Stølting Brodal (1996). Worst-case efficient priority queues. Proc. 7th ACM-SIAM Symposium on Discrete Algorithms, pp. 52–58]
While having better asymptotic bounds than other priority queue structures, they are, in the words of Brodal himself, "quite complicated" and "
otapplicable in practice."
Brodal and
Okasaki describe a
persistent (
purely functional) version of Brodal queues.
[Gerth Stølting Brodal and Chris Okasaki (1996)]
Optimal purely functional priority queues
Journal of Functional Programming.
Summary of running times
References
Heaps (data structures)
{{algorithm-stub