In
computer science
Computer science is the study of computation, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied science, ...
, the Brodal queue is a
heap/
priority queue
In computer science, a priority queue is an abstract data type similar to a regular queue (abstract data type), queue or stack (abstract data type), stack abstract data type.
In a priority queue, each element has an associated ''priority'', which ...
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.
[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
Gerth Stølting Brodal
Gerth Stølting Brodal is a professor at the
University of Aarhus,
Denmark
Denmark is a Nordic countries, Nordic country in Northern Europe. It is the metropole and most populous constituent of the Kingdom of Denmark,, . also known as the Danish Realm, a constitutionally unitary state that includes the Autonomous a ...
.
He is best known for the Brodal queue.
References
Heaps (data structures)
{{algorithm-stub