Brodal queue

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

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]

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]

Definition

A Brodal queue is a set of two trees ${\displaystyle T_{1}}$ and ${\displaystyle T_{2}}$ and 5 guides. The definition of the guide data structure can be found in the following section. For both trees, each node has a rank, this rank is useful for later operations and intuitively corresponds to the logarithm of the size of the subtree rooted in the node. We note ${\displaystyle {\text{arity}}_{i}(x)}$ the number of children of the node ${\displaystyle x}$ with rank ${\displaystyle i}$. We will also use ${\displaystyle t_{1}}$ for the root of tree ${\displaystyle T_{1}}$ and ${\displaystyle t_{2}}$ for the root of tree ${\displaystyle T_{2}}$. At each given time, every subtree rooted in a node needs to fulfill these 5 invariants :

• ${\displaystyle {\text{LEAF-RANK}}}$ : If ${\displaystyle x}$ is a leaf, then ${\displaystyle {\text{rank}}(x)=0}$,
• ${\displaystyle {\text{PARENT-RANK}}}$ : ${\displaystyle {\text{rank}}(x)<{\text{rank}}({\text{parent}}(x))}$,
• ${\displaystyle {\text{NEXT-RANK-ARITY}}}$ : If ${\displaystyle {\text{rank}}(x)>0}$, then ${\displaystyle {\text{arity}}_{{\text{rank}}(x)-1}(x)\geqslant 2}$,
• ${\displaystyle {\text{ARITY-BOUND}}}$: ${\displaystyle {\text{arity}}_{i}(x)\in \{0,2,3,\dots ,7\}}$ we highlight that ${\displaystyle {\text{arity}}_{i}(x)\neq 1}$,
• ${\displaystyle {\text{ROOT-RANK}}}$ : ${\displaystyle T_{2}=\emptyset }$ or ${\displaystyle {\text{rank}}(t_{1})\leqslant {\text{rank}}(t_{2})}$.

Here ${\displaystyle {\text{NEXT-RANK-ARITY}}}$ guaranties us that the size of the subtree rooted in a node is at least exponential to the rank of that node. In addition, ${\displaystyle {\text{ARITY-BOUND}}}$ bounds the number of children of each rank for a given node, this implies that all nodes have rank and degrees in ${\displaystyle O(\log n)}$.

In a Brodal queue, not every node will have a bigger value than its parent, the nodes vialoating this condition will be called violating nodes. However, we want to keep the number of violating nodes relatively small. To keep track of violating nodes, we create for each node two sets ${\displaystyle V(x)}$ and ${\displaystyle W(x)}$ of nodes larger than ${\displaystyle x}$. Intuitively, ${\displaystyle V(x)}$ are the nodes larger of ${\displaystyle x}$ with large rank (such that ${\displaystyle y\in V(x)}$ if ${\displaystyle {\text{rank}}(y)\geqslant {\text{rank}}(t_{1})}$), and ${\displaystyle W(x)}$ are the nodes with small rank (${\displaystyle {\text{rank}}(y)<{\text{rank}}(t_{1})}$). These sets are implemented using doubly linked list meanung they have an order. In particular, all violating nodes added to ${\displaystyle V(x)}$ are added at the front of the list, and all violating nodes added to ${\displaystyle W(x)}$ are inserted next to a node of same rank. The ${\displaystyle V(x)}$ and ${\displaystyle W(x)}$ lists fulfill these 5 invariants (we let ${\displaystyle w_{i}(x)}$ denote the number of nodes in ${\displaystyle W(x)}$ of rank ${\displaystyle i}$):

• ${\displaystyle {\text{MINIMUM-NODE}}}$ : ${\displaystyle t_{1}=\min(T_{1}\cup T_{2})}$
• ${\displaystyle {\text{VIOLATING-CONDITION}}}$ : If ${\displaystyle y\in V(x)\cup W(x)}$ then ${\displaystyle y\geqslant x}$
• ${\displaystyle {\text{PARENT-VIOLATING}}}$: If ${\displaystyle y<{\text{parent}}(y)}$ then there exist a node ${\displaystyle x\neq y}$ such that ${\displaystyle y\in V(x)\cup W(x)}$
• ${\displaystyle {\text{W-RANK-BOUND}}}$: ${\displaystyle w_{i}(x)\leqslant 6}$
• ${\displaystyle {\text{V-RANK-BOUND}}}$: By denoting ${\displaystyle V(x)=(v_{|V(x)|},\dots ,v_{2},v_{1})}$, we have: ${\displaystyle {\text{rank}}(v_{i})\geqslant \left\lfloor {\frac {i-1}{\alpha }}\right\rfloor }$ for a certain constant ${\displaystyle \alpha }$.

The guide data structure

This definition is based on the definition from Brodal's paper ^[1] .

We assume that we have a sequence of variables ${\displaystyle x_{k},\dots ,x_{1}}$ and we want to make sure that ${\displaystyle \forall i\leqslant k,x_{i}\leqslant T}$ for some threshold ${\displaystyle T}$. The only operation allowed is ${\displaystyle {\text{REDUCE}}(i)}$ which decreases ${\displaystyle x_{i}}$ by at least 2 and increases ${\displaystyle x_{i+1}}$ by at most 1. We can assume without loss of generality that ${\displaystyle {\text{REDUCE}}(i)}$ reduces ${\displaystyle x_{i}}$ by 2 and increases ${\displaystyle x_{i+1}}$by 1.

If a ${\displaystyle x_{j}}$ is increased by one, the goal of the guide is to tell us on which indices ${\displaystyle i}$ to apply ${\displaystyle {\text{REDUCE}}(i)}$ in order to respect the threshold. The guide is only allowed to make ${\displaystyle O(1)}$ calls to the ${\displaystyle {\text{REDUCE}}}$ function for each increase.

The guide has access to another sequence ${\displaystyle x'_{k},\dots ,x'_{1}}$ such that ${\displaystyle x_{i}\leqslant x'_{i}}$ and ${\displaystyle x'_{i}\in \{T-2,T-1,T\}}$. As long as after the increase of ${\displaystyle x_{j}}$ we have ${\displaystyle x_{j}\leqslant x'_{j}}$ we do not need to ask help from our guide since ${\displaystyle x_{j}}$ is "far" bellow ${\displaystyle T}$. However, if ${\displaystyle x_{j}=x'_{j}}$ before the increase, then we have ${\displaystyle x_{j}+1>x'_{j}}$ after the change.

To simplify the explanation, we can assume that ${\displaystyle T=2}$, so that ${\displaystyle x'_{i}\in \{0,1,2\}}$. The guide will create blocks in the sequence of ${\displaystyle x'_{i}}$ of form ${\displaystyle 2,1,1,\dots ,1,0}$ where we allow there to be no ${\displaystyle 1}$. The guide maintains the invariant that each element which isn't in a block is either a ${\displaystyle 1}$ or a ${\displaystyle 0}$. For example, here are the blocks for a sequence of ${\displaystyle x'_{i}}$.

${\displaystyle 1,{\underline {2,1,1,0}},1,1,{\underline {2,0}},{\underline {2,0}},1,0,{\underline {2,1,0}}}$

The guide is composed of 3 arrays :

• ${\displaystyle x}$ the array of ${\displaystyle x_{k},\dots ,x_{1}}$
• ${\displaystyle x'}$the array of ${\displaystyle x'_{k},\dots ,x'_{1}}$
• ${\displaystyle p}$ an array of pointers where all the ${\displaystyle p_{i}}$ for which ${\displaystyle x'_{i}}$ are in the same block will point to the same memory cell containing a value. If a ${\displaystyle x'_{i}}$ is not in a block, then ${\displaystyle p_{i}}$ points to a memory cell containing ${\displaystyle \bot }$.

With this definition, a guide has two important properties :

1. For each element in a block, we can find the most left element of the block in time ${\displaystyle O(1)}$.
2. We can destroy a block in time ${\displaystyle O(1)}$ by assigning ${\displaystyle \bot }$ to the memory cell pointed to by each element of the block.

This way, the guide is able to decide which indices to ${\displaystyle {\text{REDUCE}}}$ in time ${\displaystyle O(1)}$. Here is an example :

${\displaystyle {\begin{array}{ll}{\underline {2,1,1,0}},{\underline {2,1,1,1,0}}&\\{\underline {2,1,1,0}},{\underline {2,{\color {red}2},1,1,0}}&{\text{Increment }}x'_{i}\\{\underline {2,1,1,{\color {green}1}}},{\underline {{\color {blue}0},2,1,1,0}}&{\text{REDUCE}}\\{\underline {2,1,1,1}},{\underline {{\color {green}1},{\color {blue}0},1,1,0}}&{\text{REDUCE}}\\{\underline {2,1,1,1,1,0}},1,1,0&{\text{reestablish blocks}}\\\end{array}}}$

To reestablish the blocks, the pointers of the 1 and 0 added to the first block now point to the same cell as all the other elements from the first block, and the value of the second block's cell is changed to ${\displaystyle \bot }$. In the previous example, only two ${\displaystyle {\text{REDUCE}}}$ operations were needed, this is actually the case for all instances. Therefore, the queue only needs ${\displaystyle O(1)}$ operations to reestablish the property.

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.

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.
3. Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. (1990). Introduction to Algorithms (1st ed.). MIT Press and McGraw-Hill. ISBN   0-262-03141-8.
4. Sleator, Daniel Dominic; Tarjan, Robert Endre (February 1986). "Self-Adjusting Heaps". SIAM Journal on Computing . 15 (1): 52–69. CiteSeerX   10.1.1.93.6678 . doi:10.1137/0215004. ISSN   0097-5397.
5. Tarjan, Robert (1983). "3.3. Leftist heaps". Data Structures and Network Algorithms. pp. 38–42. doi:10.1137/1.9781611970265. ISBN   978-0-89871-187-5.
6. Hayward, Ryan; McDiarmid, Colin (1991). "Average Case Analysis of Heap Building by Repeated Insertion" (PDF). J. Algorithms. 12: 126–153. CiteSeerX   10.1.1.353.7888 . doi:10.1016/0196-6774(91)90027-v. Archived from the original (PDF) on 2016-02-05. Retrieved 2016-01-28.
7. "Binomial Heap | Brilliant Math & Science Wiki". brilliant.org. Retrieved 2019-09-30.
8. Brodal, Gerth Stølting; Okasaki, Chris (November 1996), "Optimal purely functional priority queues", Journal of Functional Programming, 6 (6): 839–857, doi: 10.1017/s095679680000201x
9. Okasaki, Chris (1998). "10.2. Structural Abstraction". Purely Functional Data Structures (1st ed.). pp. 158–162. ISBN   9780521631242.
10. Takaoka, Tadao (1999), Theory of 2–3 Heaps (PDF), p. 12
11. Iacono, John (2000), "Improved upper bounds for pairing heaps", Proc. 7th Scandinavian Workshop on Algorithm Theory (PDF), Lecture Notes in Computer Science, vol. 1851, Springer-Verlag, pp. 63–77, arXiv: 1110.4428 , CiteSeerX   10.1.1.748.7812 , doi:10.1007/3-540-44985-X_5, ISBN   3-540-67690-2
12. Fredman, Michael Lawrence (July 1999). "On the Efficiency of Pairing Heaps and Related Data Structures" (PDF). Journal of the Association for Computing Machinery . 46 (4): 473–501. doi:10.1145/320211.320214.
13. Pettie, Seth (2005). Towards a Final Analysis of Pairing Heaps (PDF). FOCS '05 Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science. pp. 174–183. CiteSeerX   10.1.1.549.471 . doi:10.1109/SFCS.2005.75. ISBN   0-7695-2468-0.
14. Haeupler, Bernhard; Sen, Siddhartha; Tarjan, Robert E. (November 2011). "Rank-pairing heaps" (PDF). SIAM J. Computing. 40 (6): 1463–1485. doi:10.1137/100785351.
15. Fredman, Michael Lawrence; Tarjan, Robert E. (July 1987). "Fibonacci heaps and their uses in improved network optimization algorithms" (PDF). Journal of the Association for Computing Machinery . 34 (3): 596–615. CiteSeerX   10.1.1.309.8927 . doi:10.1145/28869.28874.
16. Brodal, Gerth Stølting; Lagogiannis, George; Tarjan, Robert E. (2012). Strict Fibonacci heaps (PDF). Proceedings of the 44th symposium on Theory of Computing - STOC '12. pp. 1177–1184. CiteSeerX   10.1.1.233.1740 . doi:10.1145/2213977.2214082. ISBN   978-1-4503-1245-5.
17. Brodal, Gerth S. (1996), "Worst-Case Efficient Priority Queues" (PDF), Proc. 7th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 52–58
18. Goodrich, Michael T.; Tamassia, Roberto (2004). "7.3.6. Bottom-Up Heap Construction". Data Structures and Algorithms in Java (3rd ed.). pp. 338–341. ISBN   0-471-46983-1.
19. "Website of Gerth Stølting Brodal, at the University of Aarhus" . Retrieved 18 February 2016.