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]

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 (which will be later called ${\displaystyle {\text{RANK}}}$ 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}}}$ guarantees 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 meaning 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. We let ${\displaystyle w_{i}(x)}$ denote the number of nodes in ${\displaystyle W(x)}$ of rank ${\displaystyle i}$The ${\displaystyle V(x)}$ and ${\displaystyle W(x)}$ lists fulfill these 5 invariants (we will call the ${\displaystyle {\text{SETS}}}$ invariants):

• ${\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 }$.

Since all nodes have rank in ${\displaystyle O(\log n)}$ the ${\displaystyle {\text{W-RANK-BOUND}}}$ and ${\displaystyle {\text{V-RANK-BOUND}}}$, all ${\displaystyle V(x)}$ and ${\displaystyle W(x)}$ are in size ${\displaystyle O(\log n)}$.

We also have some invariants of the roots of the trees ${\displaystyle T_{1}}$ and ${\displaystyle T_{2}}$: ${\displaystyle t_{1}}$ and ${\displaystyle t_{2}}$ (called the ${\displaystyle {\text{ROOTS}}}$ invariants).

• ${\displaystyle {\text{ROOT-ARITY}}}$ : ${\displaystyle t_{i}\in \{2,3,\dots ,7\}{\text{ for }}i\in \{0,1,\dots ,{\text{rank}}(t_{i})-1\}}$,
• ${\displaystyle {\text{V-SIZE-BOUND}}}$: ${\displaystyle |V(x)|\leqslant \alpha {\text{ rank}}(t_{1})}$,
• ${\displaystyle {\text{W-ELEMENTS-RANK}}}$: if ${\displaystyle y\in W(t_{1})}$, then ${\displaystyle {\text{rank}}(y)<{\text{rank}}(t_{1})}$.

The ${\displaystyle {\text{V-SIZE-BOUND}}}$ invariant essentially tells us that if we increase the rank of ${\displaystyle t_{1}}$ by one, we have at most ${\displaystyle \alpha }$ new "large" violations (here large means having a high rank) without violating the ${\displaystyle {\text{V-RANK-BOUND}}}$ invariant. On the other hand the ${\displaystyle {\text{W-ELEMENTS-RANK}}}$invariant tells us that all violations in ${\displaystyle W(x)}$ are "small", this invariant is true per the definition of ${\displaystyle W}$. Maintaining the invariants ${\displaystyle {\text{W-RANK-BOUND}}}$ and ${\displaystyle {\text{ROOT-ARITY}}}$ is not trivial, to maintain these we will use the ${\displaystyle {\text{DecreaseKey}}}$ operation which can be implemented using a guide as defined in the next section. Each time we will call the ${\displaystyle {\text{DecreaseKey}}}$ operation, we will essentially :

1. Add the new violation to ${\displaystyle V(t_{1})}$ or ${\displaystyle W(t_{1})}$ depending on the rank of that violation.
2. To avoid ${\displaystyle V(t_{1})}$ and ${\displaystyle W(t_{1})}$ from getting too large, we incrementally do two kinds of transformations:
   1. Moving the sons of ${\displaystyle t_{2}}$ to ${\displaystyle t_{1}}$ to increase the rank of ${\displaystyle t_{1}}$
   2. Reducing the number of violations in ${\displaystyle W(t_{1})}$ by replacing two violations of rank ${\displaystyle k}$ to one violation of rank ${\displaystyle k+1}$

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

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}}$.

${\textstyle 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.

To implement the different priority queue operations we first need to describe some essential transformations for the trees.

To link trees, we need three nodes ${\displaystyle x_{1},x_{2}{\text{ and }}x_{3}}$of equal rank. We can calculate the minimum of these three nodes with two comparisons. Here we assume that ${\displaystyle x_{1}}$ is the minimum but the process is similar for all ${\displaystyle x_{i}}$. We can now make the nodes ${\displaystyle x_{2}}$ and ${\displaystyle x_{3}}$ the two leftmost sons of ${\displaystyle x_{1}}$ and increase the rank of ${\displaystyle x_{1}}$ by one. This preserves all the ${\displaystyle {\text{RANK}}}$ and ${\displaystyle {\text{SETS}}}$ invariants.

If ${\displaystyle x}$ has exactly two or three sons of rank ${\displaystyle {\text{rank}}(x)-1}$, we can remove these sons and ${\displaystyle x}$ gets the rank of its new largest son plus one. From the ${\displaystyle {\text{ARITY-BOUND}}}$ condition, we know that that the ${\displaystyle {\text{NEXT-RANK-ARITY}}}$ invariant will be preserved. Then, all the ${\displaystyle {\text{RANK}}}$ and ${\displaystyle {\text{SETS}}}$ invariants remain satisfied. If ${\displaystyle x}$ has 4 or more children, we can simply cut of two of them and all the invariants remain true. Therefore, the delinking of a tree of rank ${\displaystyle k}$ will always result in two or three trees of rank ${\displaystyle k-1}$ (from the 2 or 3 children cut off) and one additional tree of rank at most ${\displaystyle k}$.

When we add and remove sons of a root, we want to keep the ${\displaystyle {\text{ROOT-RANK}}}$ invariant true. For this purpose, we use 4 guides, two for each roots ${\displaystyle t_{1}}$ and ${\displaystyle t_{2}}$. To have constant time access to the son of ${\displaystyle t_{1}}$ we create an extendible array of pointed that has for each rank ${\displaystyle i\in \{0,\dots ,{\text{rank}}(t_{1})-1\}}$ a pointer to a son of ${\displaystyle t_{1}}$ of rank ${\displaystyle i}$. One guide will maintain the condition that ${\displaystyle {\text{arity}}_{i}(t_{1})\leqslant 7}$ and the other maintains ${\displaystyle {\text{arity}}_{i}(t_{1})\geqslant 2}$ both for ${\displaystyle i\in \{0,\dots ,{\text{rank}}(t_{1})-3\}}$. The sons of ${\displaystyle t_{1}}$of rank ${\displaystyle {\text{rank}}(t_{1})-1}$ and ${\displaystyle {\text{rank}}(t_{1})-2}$ are treated separately in a straight forward way to maintant their number between 2 and 7. The equivalent to the ${\displaystyle x'_{i}}$ variable in the definition of the guide will have the values ${\displaystyle \{5,6,7\}}$ for the higher bound guide and ${\displaystyle \{4,3,2\}}$ for the lower bound.

In this context, when we add a child of rank ${\displaystyle i}$ to the root, we increase ${\displaystyle x'_{i}}$ by one, and apply the ${\displaystyle {\text{REDUCE}}}$ operations. The ${\displaystyle {\text{RECUCE}}(i)}$ operation here consists of linking three trees of rank ${\displaystyle i}$ which creates a new child of rank ${\displaystyle i+1}$. Therefore, we decrease ${\displaystyle {\text{arity}}_{i}(t_{1})}$ by three and increase ${\displaystyle {\text{arity}}_{i+1}(t_{1})}$ by one. If this increase results in too many sons of rank ${\displaystyle {\text{rank}}(t_{1})-2}$ or ${\displaystyle {\text{rank}}(t_{1})-1}$ we link some of these sons together and possibly increase the rank of ${\displaystyle t_{1}}$. If we increase the rank of ${\displaystyle t_{1}}$, we have to increase the length of the extendible array managed by the guides.

Cutting off a son from ${\displaystyle t_{1}}$ is very similar, except here the ${\displaystyle {\text{REDUCE}}}$ operation corresponds to the delinking of a tree.

For the root ${\displaystyle t_{2}}$ the situation is nearly the same. However, since ${\displaystyle {\text{MINIMUM-NODE}}}$ guarantees us that ${\displaystyle t_{1}}$ is the minimum element, we know that we won't create any violation by linking or delinking children of ${\displaystyle t_{1}}$. The same cannot be said for ${\displaystyle t_{2}}$. Linking sons will never create new violations but the delinking of sons can create up to three new violations. The tree left over by a delinking is made a son of ${\displaystyle t_{1}}$ if it has rank less than ${\displaystyle {\text{rank}}(t_{1})}$ and otherwise it becomes a son of ${\displaystyle t_{2}}$. The new violations which have rank larger than ${\displaystyle {\text{rank}}(t_{1})}$ are added to ${\displaystyle V(t_{1})}$. To maintain the invariants on the ${\displaystyle V(t_{1})}$ set (namely ${\displaystyle {\text{V-RANK-BOUND}}}$ and ${\displaystyle {\text{V-SIZE-BOUND}}}$), we have to guarantee that the rank of ${\displaystyle t_{1}}$ will be increased and that ${\displaystyle \alpha }$ in those invariants is chosen large enough.

The goal of this transformation is to reduce the total amount of potential violations, meaning reducing ${\displaystyle \left|\bigcup _{x\in T_{1}\cup T_{2}}V(x)\cup W(x)\right|}$.

We assume we have two potential violations ${\displaystyle x_{1}}$ and ${\displaystyle x_{2}}$ of equal rank ${\displaystyle k}$. We then have several cases:

1. If one of the nodes turns out not to be a violation, we just remove it from its corresponding violation set.
2. Otherwise, both nodes are violations. Because of ${\displaystyle {\text{ARITY-BOUND}}}$, we know that both ${\displaystyle x_{1}}$ and ${\displaystyle x_{2}}$ have at least one brother. Then:
   1. If ${\displaystyle x_{1}}$ and ${\displaystyle x_{2}}$ are not brothers, then we can assume without losing generality that ${\displaystyle {\text{parent}}(x_{1})\leqslant {\text{parent}}(x_{2})}$, we can then swap the subtrees rooted in ${\displaystyle x_{1}}$ and ${\displaystyle x_{2}}$. The number of violations can only go down during that swap.
   2. Else, ${\displaystyle x_{1}}$ and ${\displaystyle x_{2}}$ are brothers of a node we will call ${\displaystyle y}$.
      1. If ${\displaystyle x_{1}}$ has more than one brother of rank ${\displaystyle k}$, we can just cut off ${\displaystyle x_{1}}$ and make it a non violating node of ${\displaystyle t_{1}}$as described in the previous subsection.
      2. Else, ${\displaystyle x_{1}}$ and ${\displaystyle x_{2}}$ are the only children of rank ${\displaystyle k}$ of ${\displaystyle y}$..
         1. If ${\displaystyle {\text{rank}}(y)>k+1}$, we can cut off both ${\displaystyle x_{1}}$ and ${\displaystyle x_{2}}$ nodes from ${\displaystyle y}$ and make them non violating nodes of ${\displaystyle t_{1}}$ as described in the previous subsection
         2. Else, ${\displaystyle {\text{rank}}(y)=k+1}$. We will cut off ${\displaystyle x_{1},x_{2}{\text{ and }}y}$, the new rank of ${\displaystyle y}$ will be one plus the rank of its leftmost son, We replace ${\displaystyle y}$ by a son on ${\displaystyle t_{1}}$ of rank ${\displaystyle k+1}$, which can be cut off as described in the previous subsection. If the replacement for ${\displaystyle y}$ becomes a violating node of rank ${\displaystyle k+1}$, we add it to ${\displaystyle W(t_{1})}$. Finally we make ${\displaystyle x_{1},x_{2}{\text{ and }}y}$ new sons of ${\displaystyle t_{1}}$ as described above.

The only violation sets where we will add violations are ${\displaystyle V(t_{1})}$ and ${\displaystyle W(t_{1})}$. As described above, the invariants on those sets are maintained using guides. When we add a violation to ${\displaystyle W(t_{1})}$ we have two cases:

1. If there are exactly 6 violations of the given rank and there are at least two violating nodes which aren't sons of ${\displaystyle t_{2}}$, we apply the ${\displaystyle {\text{REDUCE}}}$ operations given by the guide.
2. If there are more than 4 violations which are sons of ${\displaystyle t_{2}}$, we cut the additional violations off and link them below ${\displaystyle t_{1}}$. This removes the violation created by these nodes and doesn't affect the guide maintaining the sons of ${\displaystyle t_{2}}$.

For each priority queue operation that is performed, we increase the rank of ${\displaystyle t_{1}}$ by at least one by moving a constant number of sons of ${\displaystyle t_{2}}$ to ${\displaystyle t_{1}}$ (provided that ${\displaystyle T_{2}\neq \emptyset }$). Increasing the rank of ${\displaystyle t_{1}}$ allows us to add violations to ${\displaystyle V(t_{1})}$ while still maintaining all our invariants. If ${\displaystyle T_{2}\neq \emptyset }$ and ${\displaystyle {\text{rank}}(t_{2})\leqslant {\text{rank}}(t_{1})+2}$ we can cut the largest sons of ${\displaystyle t_{2}}$, link them to ${\displaystyle t_{1}}$ and then make ${\displaystyle t_{2}}$ a son of ${\displaystyle t_{1}}$. This satisfies all the invariants. Otherwise, we cut off a son of ${\displaystyle t_{2}}$ of rank ${\displaystyle {\text{rank}}(t_{1})+2}$, delink this son and add the resulting trees to ${\displaystyle t_{1}}$. If ${\displaystyle T_{2}=\emptyset }$, we know that ${\displaystyle t_{1}}$ is the node of largest rank, therefore we know that no large violations can be created.

${\displaystyle {\text{MakeQueue}}()}$ just returns a pair of empty trees.

${\displaystyle {\text{FindMin}}(Q)}$ returns ${\displaystyle t_{1}}$.

${\displaystyle {\text{Insert}}(Q,e)}$ is only a special case of ${\displaystyle {\text{Meld}}(Q_{1},Q_{2})}$ where ${\displaystyle Q_{2}}$ is a queue only containing ${\displaystyle e}$ and ${\displaystyle Q_{1}=Q}$.

${\displaystyle {\text{Meld}}(Q_{1},Q_{2})}$ involves four trees (two for each queue). The tree having the minimum root becomes the new ${\displaystyle T_{1}}$ tree. If this tree is also the tree of maximum rank, we can add all the other trees below as described previously. In this case, no violating node is created so no transformation is done on violating nodes. Otherwise, the tree of maximum rank becomes the new ${\displaystyle T_{2}}$ tree and the other trees are added below as described in the section "Maintaining the sons of a root". If some trees have equal rank to this new ${\displaystyle T_{2}}$, we can delink them before adding them. The violations created are handled as explained in the section : "Avoiding too many violations".

${\displaystyle {\text{DecreaseKey}}(Q,e,e')}$ replaces the element of ${\displaystyle e}$ by ${\displaystyle e'}$ (with ${\displaystyle e'\leqslant e}$). If ${\displaystyle e'<t_{1}}$, we swap the two nodes, otherwise, we handle the potential new violation as explained in the section "Avoiding too many violations".

${\displaystyle {\text{DeleteMin}}(Q)}$ is allowed to take worst case time ${\displaystyle O(\log n)}$. First, we completely empty ${\displaystyle T_{2}}$ by moving all the sons of ${\displaystyle t_{2}}$ to ${\displaystyle t_{1}}$ then making ${\displaystyle t_{2}}$ a rank 0 son of ${\displaystyle t_{1}}$. Then, ${\displaystyle t_{1}}$ is deleted, this leaves us with at most ${\displaystyle O(\log n)}$ independant trees. The new minimum is then found by looking at the violating sets of the old root and looking at all the roots of the new trees. If the minimum element is not a root, we can swap a root from a tree of equal rank to it. This creates at most one violation. Then, we make the independant trees sons of the new minimum element by performing ${\displaystyle O(\log n)}$ linking and delinking operations. This reestablishes the ${\displaystyle {\text{RANK}}}$ and ${\displaystyle {\text{ROOTS}}}$ invariants. By merging the ${\displaystyle V}$ and ${\displaystyle W}$ sets of the new root along with the ${\displaystyle V}$ and ${\displaystyle W}$ sets of the old root together, we get one new violation set of size ${\displaystyle O(\log n)}$. By doign at most ${\displaystyle O(\log n)}$ violation reducing tranformations we can make the violation set only contain at most one element of each rank. This set will be our new ${\displaystyle W}$ set and the new ${\displaystyle V}$ set is empty. This reestablishes the ${\displaystyle {\text{SETS}}}$ invariants. We also have to initialise a new guide for the new root ${\displaystyle t_{1}}$.

Here, ${\displaystyle -\infty }$ denotes the smallest possible element. ${\displaystyle {\text{Delete}}(Q,e)}$ can simply be implemented by calling ${\displaystyle {\text{DecreaseKey}}(Q,e,-\infty )}$ followed by ${\displaystyle {\text{DeleteMin}}(Q)}$.

In this section, we summarize some implementation details for the Brodal Queue data structure.

In each tree, each node is a record having the following fields:

• The element associated with the node (its value),
• The rank of the node,
• pointers to the node's left and right brothers,
• a pointer to the father node,
• a pointer to the leftmost son,
• pointers to the first element of the node's ${\displaystyle V}$ and ${\displaystyle W}$ sets,
• pointers to the following and previous element in the violation set the node belongs to. If this node is the first node of the violation set ${\displaystyle V(x)}$ or ${\displaystyle W(x)}$ it belongs to, the previous pointer points to ${\displaystyle x}$.
• an array of pointers to sons of ${\displaystyle t_{1}}$ of rank ${\displaystyle i}$ (with ${\displaystyle i\in \{0,\dots ,{\text{rank}}(t_{1})-1\}}$),
• a similar array for ${\displaystyle t_{2}}$,
• an array of pointers to nodes in ${\displaystyle W(t_{1})}$ of rank ${\displaystyle i}$ (with ${\displaystyle i\in \{0,\dots ,{\text{rank}}(t_{1})-1\}}$).

Finally, we have 5 guides: three to maintain the upper bounds on ${\displaystyle {\text{arity}}_{i}(t_{1})}$, ${\displaystyle {\text{arity}}_{i}(t_{2})}$ and ${\displaystyle w_{i}(t_{1})}$ and two to maintain the lower bounds on ${\displaystyle {\text{arity}}_{i}(t_{1})}$ and ${\displaystyle {\text{arity}}_{i}(t_{2})}$.

Due to its high amount of pointers and sets to keep track of, the Brodal Queue is extremely hard to implement. For this reason it is best described as a purely theoretical object to lower time complexity on algorithms like Dijkstra's algorithm. However, the Brodal has been implemented in Scala (the github repository can be found here: https://github.com/ruippeixotog/functional-brodal-queues). In his paper, Gerth Stølting Brodal mentions that: "An important issue for further work is to simplify the construction to make it applicable in practice"^[3].

Here are time complexities^[4] 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[4]	Θ(1)	Θ(log n)	Θ(log n)	Θ(log n)	Θ(n)	Θ(n)
Skew[5]	Θ(1)	O(log n) am.	O(log n) am.	O(log n) am.	O(log n) am.	Θ(n) am.
Leftist[6]	Θ(1)	Θ(log n)	Θ(log n)	Θ(log n)	Θ(log n)	Θ(n)
Binomial[4][8]	Θ(1)	Θ(log n)	Θ(log n)	Θ(1) am.	Θ(log n)[b]	Θ(n)
Skew binomial[9]	Θ(1)	Θ(log n)	Θ(log n)	Θ(1)	Θ(log n)[b]	Θ(n)
2–3 heap[11]	Θ(1)	O(log n) am.	Θ(1)	Θ(1) am.	O(log n)[b]	Θ(n)
Bottom-up skew[5]	Θ(1)	O(log n) am.	O(log n) am.	Θ(1) am.	Θ(1) am.	Θ(n) am.
Pairing[12]	Θ(1)	O(log n) am.	o(log n) am.[c]	Θ(1)	Θ(1)	Θ(n)
Rank-pairing[15]	Θ(1)	O(log n) am.	Θ(1) am.	Θ(1)	Θ(1)	Θ(n)
Fibonacci[4][16]	Θ(1)	O(log n) am.	Θ(1) am.	Θ(1)	Θ(1)	Θ(n)
Strict Fibonacci[17][d]	Θ(1)	Θ(log n)	Θ(1)	Θ(1)	Θ(1)	Θ(n)
Brodal[18][d]	Θ(1)	Θ(log n)	Θ(1)	Θ(1)	Θ(1)	Θ(n)[19]

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