Brodal queue

In computer science, the Brodal queue is a heap/priority queue structure with very low worst case time bounds: ${\displaystyle O(1)}$ for insertion, find-minimum, meld (merge two queues) and decrease-key and ${\displaystyle O(\mathrm {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]

Brodal queue
Type	Heap/priority queue
Invented	1996
Invented by	Gerth Stølting Brodal
Time complexity in big O notation Operation Average Worst case Space complexity

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]

Summary of running times

Here are time complexities^[3] of various heap data structures. The abbreviation am. indicates that the given complexity is amortized, otherwise it is a worst-case complexity. For the meaning of "O(f)" and "Θ(f)" see Big O notation. Names of operations assume a min-heap.

Operation	find-min	delete-min	decrease-key	insert	meld	make-heap[a]
Binary[3]	Θ(1)	Θ(log n)	Θ(log n)	Θ(log n)	Θ(n)	Θ(n)
Skew[4]	Θ(1)	O(log n) am.	O(log n) am.	O(log n) am.	O(log n) am.	Θ(n) am.
Leftist[5]	Θ(1)	Θ(log n)	Θ(log n)	Θ(log n)	Θ(log n)	Θ(n)
Binomial[3][7]	Θ(1)	Θ(log n)	Θ(log n)	Θ(1) am.	Θ(log n)[b]	Θ(n)
Skew binomial[8]	Θ(1)	Θ(log n)	Θ(log n)	Θ(1)	Θ(log n)[b]	Θ(n)
2–3 heap[10]	Θ(1)	O(log n) am.	Θ(1)	Θ(1) am.	O(log n)[b]	Θ(n)
Bottom-up skew[4]	Θ(1)	O(log n) am.	O(log n) am.	Θ(1) am.	Θ(1) am.	Θ(n) am.
Pairing[11]	Θ(1)	O(log n) am.	o(log n) am.[c]	Θ(1)	Θ(1)	Θ(n)
Rank-pairing[14]	Θ(1)	O(log n) am.	Θ(1) am.	Θ(1)	Θ(1)	Θ(n)
Fibonacci[3][15]	Θ(1)	O(log n) am.	Θ(1) am.	Θ(1)	Θ(1)	Θ(n)
Strict Fibonacci[16][d]	Θ(1)	Θ(log n)	Θ(1)	Θ(1)	Θ(1)	Θ(n)
Brodal[17][d]	Θ(1)	Θ(log n)	Θ(1)	Θ(1)	Θ(1)	Θ(n)[18]

1. make-heap is the operation of building a heap from a sequence of n unsorted elements. It can be done in Θ(n) time whenever meld runs in O(log n) time (where both complexities can be amortized).^[4][5] Another algorithm achieves Θ(n) for binary heaps.^[6]
2. For persistent heaps (not supporting decrease-key), a generic transformation reduces the cost of meld to that of insert, while the new cost of delete-min is the sum of the old costs of delete-min and meld.^[9] Here, it makes meld run in Θ(1) time (amortized, if the cost of insert is) while delete-min still runs in O(log n). Applied to skew binomial heaps, it yields Brodal-Okasaki queues, persistent heaps with optimal worst-case complexities.^[8]
3. Lower bound of ${\displaystyle \Omega (\log \log n),}$^[12] upper bound of ${\displaystyle O(2^{2{\sqrt {\log \log n}}}).}$^[13]
4. Brodal queues and strict Fibonacci heaps achieve optimal worst-case complexities for heaps. They were first described as imperative data structures. The Brodal-Okasaki queue is a persistent data structure achieving the same optimum, except that decrease-key is not supported.

Gerth Stølting Brodal

Gerth Stølting Brodal is a professor at the University of Aarhus, Denmark.^[19] He is best known for the Brodal queue.