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]

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.