Brodal queue explained

Brodal queue
Type:Heap/priority queue
Invented By:Gerth Stølting Brodal
Invented Year:1996

In computer science, the Brodal queue is a heap/priority queue structure with very low worst case time bounds:

O(1)

for insertion, find-minimum, meld (merge two queues) and decrease-key and

O(log(n))

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]

References

  1. Gerth Stølting Brodal (1996). Worst-case efficient priority queues. Proc. 7th ACM-SIAM Symposium on Discrete Algorithms, pp. 52–58
  2. Gerth Stølting Brodal and Chris Okasaki (1996). Optimal purely functional priority queues. Journal of Functional Programming.

This article is licensed under the GNU Free Documentation License. It uses material from the Wikipedia article "Brodal queue".

Except where otherwise indicated, Everything.Explained.Today is © Copyright 2009-2024, A B Cryer, All Rights Reserved. Cookie policy.