![]() | It has been suggested that
Gerth Stølting Brodal be
merged into this article. (
Discuss) Proposed since March 2024. |
Brodal queue | ||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
Type | Heap/ priority queue | |||||||||||
Invented | 1996 | |||||||||||
Invented by | Gerth Stølting Brodal | |||||||||||
|
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]
Here are time complexities [3] of various heap data structures. Function names assume a min-heap. For the meaning of "O(f)" and "Θ(f)" see Big O notation.
Operation | find-min | delete-min | insert | decrease-key | meld |
---|---|---|---|---|---|
Binary [3] | Θ(1) | Θ(log n) | O(log n) | O(log n) | Θ(n) |
Leftist | Θ(1) | Θ(log n) | Θ(log n) | O(log n) | Θ(log n) |
Binomial [3] [4] | Θ(1) | Θ(log n) | Θ(1) [a] | Θ(log n) | O(log n) |
Skew binomial [5] | Θ(1) | Θ(log n) | Θ(1) | Θ(log n) | O(log n) [b] |
Pairing [6] | Θ(1) | O(log n) [a] | Θ(1) | o(log n) [a] [c] | Θ(1) |
Rank-pairing [9] | Θ(1) | O(log n) [a] | Θ(1) | Θ(1) [a] | Θ(1) |
Fibonacci [3] [10] | Θ(1) | O(log n) [a] | Θ(1) | Θ(1) [a] | Θ(1) |
Strict Fibonacci [11] | Θ(1) | O(log n) | Θ(1) | Θ(1) | Θ(1) |
Brodal [12] [d] | Θ(1) | O(log n) | Θ(1) | Θ(1) | Θ(1) |
2–3 heap [14] | Θ(1) | O(log n) [a] | Θ(1) [a] | Θ(1) | O(log n) |
![]() | It has been suggested that
Gerth Stølting Brodal be
merged into this article. (
Discuss) Proposed since March 2024. |
Brodal queue | ||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
Type | Heap/ priority queue | |||||||||||
Invented | 1996 | |||||||||||
Invented by | Gerth Stølting Brodal | |||||||||||
|
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]
Here are time complexities [3] of various heap data structures. Function names assume a min-heap. For the meaning of "O(f)" and "Θ(f)" see Big O notation.
Operation | find-min | delete-min | insert | decrease-key | meld |
---|---|---|---|---|---|
Binary [3] | Θ(1) | Θ(log n) | O(log n) | O(log n) | Θ(n) |
Leftist | Θ(1) | Θ(log n) | Θ(log n) | O(log n) | Θ(log n) |
Binomial [3] [4] | Θ(1) | Θ(log n) | Θ(1) [a] | Θ(log n) | O(log n) |
Skew binomial [5] | Θ(1) | Θ(log n) | Θ(1) | Θ(log n) | O(log n) [b] |
Pairing [6] | Θ(1) | O(log n) [a] | Θ(1) | o(log n) [a] [c] | Θ(1) |
Rank-pairing [9] | Θ(1) | O(log n) [a] | Θ(1) | Θ(1) [a] | Θ(1) |
Fibonacci [3] [10] | Θ(1) | O(log n) [a] | Θ(1) | Θ(1) [a] | Θ(1) |
Strict Fibonacci [11] | Θ(1) | O(log n) | Θ(1) | Θ(1) | Θ(1) |
Brodal [12] [d] | Θ(1) | O(log n) | Θ(1) | Θ(1) | Θ(1) |
2–3 heap [14] | Θ(1) | O(log n) [a] | Θ(1) [a] | Θ(1) | O(log n) |