Brodal-Warteschlange

In der Informatik ist die Brodal-Warteschlange eine Heap- / Prioritätswarteschlangenstruktur mit sehr niedrigen Worst-Case -Zeitgrenzen für Einfügungen, Minimumsuche, Zusammenführen (Melden) zweier Warteschlangen und Schlüsselverringerung sowie für Minimumlöschung und allgemeine Löschungen. Sie ist die erste Heap-Variante, die diese Grenzen ohne Amortisation der Betriebskosten erreicht. Brodal-Warteschlangen sind nach ihrem Erfinder Gerth Stølting Brodal benannt. ^{[ 1 ]}${\displaystyle O(1)}$${\displaystyle O(\mathrm {log} (n))}$

Obwohl sie bessere asymptotische Schranken als andere Prioritätswarteschlangenstrukturen aufweisen, sind sie, in den Worten Brodals selbst, „ziemlich kompliziert“ und „in der Praxis nicht anwendbar“. ^{[ 1 ]} Brodal und Okasaki beschreiben eine persistente ( rein funktionale ) Version von Brodal-Warteschlangen. ^{[ 2 ]}

Eine Brodal-Warteschlange besteht aus zwei Bäumen und fünf Leitbäumen . Die Definition der Leitbaum -Datenstruktur finden Sie im folgenden Abschnitt. In beiden Bäumen hat jeder Knoten einen Rang , der für spätere Operationen nützlich ist und intuitiv dem Logarithmus der Größe des Teilbaums mit Wurzelknoten entspricht. Wir notieren die Anzahl der Kinder des Knotens mit Rang . Wir verwenden außerdem für die Wurzel des Baums und für die Wurzel des Baums . Zu jedem Zeitpunkt muss jeder Teilbaum mit Wurzelknoten die folgenden fünf Invarianten erfüllen (die später als Invarianten bezeichnet werden ): ${\displaystyle T_{1}}$${\displaystyle T_{2}}$${\displaystyle {\text{arity}}_{i}(x)}$${\displaystyle x}$${\displaystyle i}$${\displaystyle t_{1}}$${\displaystyle T_{1}}$${\displaystyle t_{2}}$${\displaystyle T_{2}}$${\displaystyle {\text{RANK}}}$

• ${\displaystyle {\text{LEAF-RANK}}}$ Wenn es sich um ein Blatt handelt, dann${\displaystyle x}$${\displaystyle {\text{rank}}(x)=0}$
• ${\displaystyle {\text{Elternrang}}}$ : ,${\displaystyle {\text{rank}}(x)<{\text{rank}}({\text{parent}}(x))}$
• ${\displaystyle {\text{NEXT-RANK-ARITY}}}$ Wenn , dann ,${\displaystyle {\text{rank}}(x)>0}$${\displaystyle {\text{arity}}_{{\text{rank}}(x)-1}(x)\geqslant 2}$
• ${\displaystyle {\text{ARITY-BOUND}}}$Wir heben hervor , dass${\displaystyle {\text{arity}}_{i}(x)\in \{0,2,3,\dots ,7\}}$${\displaystyle {\text{arity}}_{i}(x)\neq 1}$
• ${\displaystyle {\text{ROOT-RANK}}}$ : oder .${\displaystyle T_{2}=\emptyset }$${\displaystyle {\text{rank}}(t_{1})\leqslant {\text{rank}}(t_{2})}$

Hier wird sichergestellt, dass die Größe des Teilbaums mit Wurzelknoten mindestens exponentiell zum Rang dieses Knotens ist. Außerdem wird die Anzahl der Kinder jedes Rangs für einen gegebenen Knoten beschränkt; dies impliziert, dass alle Knoten den Rang und den Grad in haben . ${\displaystyle {\text{NEXT-RANK-ARITY}}}$${\displaystyle {\text{ARITY-BOUND}}}$${\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{Verstoß gegen die Auflage}}}$ : If ${\displaystyle y\in V(x)\cup W(x)}$ then ${\displaystyle y\geqslant x}$
• ${\displaystyle {\text{Elternverletzend}}}$: 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{WURZELN}}}$ invariants).

• ${\displaystyle {\text{ROOT-ARITY}}}$ : ${\displaystyle t_{i}\in \{2,3,\dots ,7\}{\text{ für }}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]

Wir gehen von einer Folge von Variablen aus und möchten sicherstellen, dass für einen bestimmten Schwellenwert gilt: Die einzige zulässige Operation ist die Subtraktion, die um mindestens 2 verringert und höchstens um 1 erhöht . Ohne Beschränkung der Allgemeinheit können wir annehmen, dass die Folge um 2 verringert und um 1 erhöht wird. ${\displaystyle x_{k},\dots ,x_{1}}$${\displaystyle \forall i\leqslant k,x_{i}\leqslant T}$${\displaystyle T}$${\displaystyle {\text{REDUCE}}(i)}$${\displaystyle x_{i}}$${\displaystyle x_{i+1}}$${\displaystyle {\text{REDUCE}}(i)}$${\displaystyle x_{i}}$${\displaystyle x_{i+1}}$

Wird a um eins erhöht, besteht die Aufgabe des Leitfadens darin, uns mitzuteilen, auf welche Indizes die Änderung angewendet werden muss , um den Schwellenwert einzuhalten. Der Leitfaden darf die Funktion nur bei jeder Erhöhung aufrufen. ${\displaystyle x_{j}}$${\displaystyle i}$${\displaystyle {\text{REDUCE}}(i)}$${\displaystyle O(1)}$${\displaystyle {\text{REDUCE}}}$

Der Leitfaden hat Zugriff auf eine weitere Sequenz, sodass und . Solange nach der Erhöhung von gilt , benötigen wir keine Hilfe vom Leitfaden, da „weit“ unter liegt . Wenn jedoch vor der Erhöhung gilt, dann gilt nach der Änderung . ${\displaystyle x'_{k},\dots ,x'_{1}}$${\displaystyle x_{i}\leqslant x'_{i}}$${\displaystyle x'_{i}\in \{T-2,T-1,T\}}$${\displaystyle x_{j}}$${\displaystyle x_{j}\leqslant x'_{j}}$${\displaystyle x_{j}}$${\displaystyle T}$${\displaystyle x_{j}=x'_{j}}$${\displaystyle x_{j}+1>x'_{j}}$

Um die Erklärung zu vereinfachen, können wir annehmen, dass , sodass . Der Leitfaden erzeugt Blöcke in der Sequenz der Form , wobei wir zulassen, dass kein vorkommt . Der Leitfaden gewährleistet die Invariante, dass jedes Element, das sich nicht in einem Block befindet, entweder ein oder ein ist . Hier sind beispielsweise die Blöcke für eine Sequenz von . ${\displaystyle T=2}$${\displaystyle x'_{i}\in \{0,1,2\}}$${\displaystyle x'_{i}}$${\displaystyle 2,1,1,\dots ,1,0}$${\displaystyle 1}$${\displaystyle 1}$${\displaystyle 0}$${\displaystyle x'_{i}}$

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

Der Leitfaden besteht aus 3 Arrays  :

• ${\displaystyle x}$die Anordnung von${\displaystyle x_{k},\dots ,x_{1}}$
• ${\displaystyle x'}$die Anordnung von${\displaystyle x'_{k},\dots ,x'_{1}}$
• ${\displaystyle p}$Ein Array von Zeigern, wobei alle Zeiger, die sich im selben Block befinden, auf dieselbe Speicherzelle verweisen, die einen Wert enthält. Befindet sich ein Zeiger nicht in einem Block, verweist er auf eine Speicherzelle, die den Wert enthält .${\displaystyle p_{i}}$${\displaystyle x'_{i}}$${\displaystyle x'_{i}}$${\displaystyle p_{i}}$${\displaystyle \bot }$

Gemäß dieser Definition besitzt ein Reiseführer zwei wichtige Eigenschaften:

1. Für jedes Element in einem Block können wir das am weitesten links stehende Element des Blocks in der Zeit finden .${\displaystyle O(1)}$
2. Wir können einen Block in der Zeit zerstören , indem wir der Speicherzelle, auf die jedes Element des Blocks zeigt, einen Wert zuweisen.${\displaystyle O(1)}$${\displaystyle \bot }$

Auf diese Weise kann der Guide entscheiden, welche Indizes im Laufe der Zeit aktualisiert werden sollen . Hier ist ein Beispiel: ${\displaystyle {\text{REDUCE}}}$${\displaystyle O(1)}$

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

Um die Blöcke wiederherzustellen, zeigen die Zeiger der 1 und 0, die dem ersten Block hinzugefügt wurden, nun auf dieselbe Zelle wie alle anderen Elemente des ersten Blocks, und der Wert der Zelle des zweiten Blocks wird geändert . Im vorherigen Beispiel waren nur zwei Operationen nötig; dies trifft tatsächlich auf alle Instanzen zu. Daher benötigt die Warteschlange nur Operationen, um die Eigenschaft wiederherzustellen. ${\displaystyle \bot }$${\displaystyle {\text{REDUCE}}}$${\displaystyle O(1)}$

Um die verschiedenen Prioritätswarteschlangenoperationen zu implementieren , müssen wir zunächst einige grundlegende Transformationen für die Bäume beschreiben.

Um Bäume zu verknüpfen, benötigen wir drei Knoten gleichen Rangs. Wir können das Minimum dieser drei Knoten mit zwei Vergleichen berechnen. Hier nehmen wir an, dass der Knoten das Minimum ist, aber das Verfahren ist für alle Knoten analog . Wir können nun die Knoten und die beiden linken Söhne von verknüpfen und den Rang von um eins erhöhen . Dadurch bleiben alle Invarianten erhalten . ${\displaystyle x_{1},x_{2}{\text{ and }}x_{3}}$${\displaystyle x_{1}}$${\displaystyle x_{i}}$${\displaystyle x_{2}}$${\displaystyle x_{3}}$${\displaystyle x_{1}}$${\displaystyle x_{1}}$${\displaystyle {\text{RANK}}}$${\displaystyle {\text{SETS}}}$

Hat der Baum genau zwei oder drei Söhne vom Rang , können wir diese Söhne entfernen und erhalten den Rang seines neuen größten Sohnes plus eins. Aus der Bedingung wissen wir, dass die Invariante erhalten bleibt. Somit bleiben alle Invarianten und erfüllt. Hat der Baum vier oder mehr Kinder, können wir einfach zwei davon entfernen, und alle Invarianten bleiben gültig. Daher führt die Entkopplung eines Baumes vom Rang stets zu zwei oder drei Bäumen vom Rang (durch das Entfernen der zwei oder drei Kinder) und höchstens einem zusätzlichen Baum vom Rang . ${\displaystyle x}$${\displaystyle {\text{rank}}(x)-1}$${\displaystyle x}$${\displaystyle {\text{ARITY-BOUND}}}$${\displaystyle {\text{NEXT-RANK-ARITY}}}$${\displaystyle {\text{RANK}}}$${\displaystyle {\text{SETS}}}$${\displaystyle x}$${\displaystyle k}$${\displaystyle k-1}$${\displaystyle k}$

Beim Hinzufügen und Entfernen von Söhnen einer Wurzel soll die Invariante erhalten bleiben. Dazu verwenden wir vier Leitfunktionen, zwei für jede Wurzel und . Um in konstanter Zeit auf den Sohn von zugreifen zu können, erstellen wir ein erweiterbares Array von Zeigern, das für jeden Rang einen Zeiger auf einen Sohn von Rang enthält . Eine Leitfunktion stellt sicher, dass gilt, die andere stellt sicher, dass beides für gilt . Die Söhne von Rang und werden auf einfache Weise separat behandelt, um ihre Anzahl zwischen 2 und 7 zu halten. Die entsprechende Variable in der Definition der Leitfunktion enthält die Werte für die obere Schranke und für die untere Schranke. ${\displaystyle {\text{ROOT-RANK}}}$${\displaystyle t_{1}}$${\displaystyle t_{2}}$${\displaystyle t_{1}}$${\displaystyle i\in \{0,\dots ,{\text{rank}}(t_{1})-1\}}$${\displaystyle t_{1}}$${\displaystyle i}$${\displaystyle {\text{arity}}_{i}(t_{1})\leqslant 7}$${\displaystyle {\text{arity}}_{i}(t_{1})\geqslant 2}$${\displaystyle i\in \{0,\dots ,{\text{rank}}(t_{1})-3\}}$${\displaystyle t_{1}}$${\displaystyle {\text{rank}}(t_{1})-1}$${\displaystyle {\text{rank}}(t_{1})-2}$${\displaystyle x'_{i}}$${\displaystyle \{5,6,7\}}$${\displaystyle \{4,3,2\}}$

In diesem Kontext erhöhen wir beim Hinzufügen eines Kindes vom Rang n zur Wurzel den Rang n um eins und wenden die Operationen an. Die Operation besteht hier darin, drei Bäume vom Rang n zu verknüpfen, wodurch ein neues Kind vom Rang n entsteht . Daher verringern wir den Rang n um drei und erhöhen ihn um eins. Falls diese Erhöhung zu viele Kinder vom Rang n erzeugt oder wir einige dieser Kinder miteinander verknüpfen und dadurch möglicherweise den Rang von n erhöhen , müssen wir die Länge des von den Leitknoten verwalteten erweiterbaren Arrays anpassen. ${\displaystyle i}$${\displaystyle x'_{i}}$${\displaystyle {\text{REDUCE}}}$${\displaystyle {\text{RECUCE}}(i)}$${\displaystyle i}$${\displaystyle i+1}$${\displaystyle {\text{arity}}_{i}(t_{1})}$${\displaystyle {\text{arity}}_{i+1}(t_{1})}$${\displaystyle {\text{rank}}(t_{1})-2}$${\displaystyle {\text{rank}}(t_{1})-1}$${\displaystyle t_{1}}$${\displaystyle t_{1}}$

Das Abschneiden eines Sohnes ist sehr ähnlich, nur dass es sich hier um die Entkopplung eines Baumes handelt. ${\displaystyle t_{1}}$${\displaystyle {\text{REDUCE}}}$

Für die Wurzel ist die Situation nahezu identisch. Da jedoch garantiert wird, dass das kleinste Element ist, wissen wir, dass wir durch Verknüpfen oder Trennen von Kindern von keine Verletzung erzeugen . Dasselbe gilt nicht für . Das Verknüpfen von Söhnen erzeugt niemals neue Verletzungen, aber das Trennen von Söhnen kann bis zu drei neue Verletzungen erzeugen. Der durch das Trennen verbleibende Baum wird zu einem Sohn von gemacht, wenn sein Rang kleiner als ist , andernfalls wird er zu einem Sohn von . Die neuen Verletzungen mit einem Rang größer als werden zu hinzugefügt . Um die Invarianten der Menge (nämlich und ) zu erhalten, müssen wir sicherstellen, dass der Rang von erhöht wird und dass in diesen Invarianten groß genug gewählt wird. ${\displaystyle t_{2}}$${\displaystyle {\text{MINIMUM-NODE}}}$${\displaystyle t_{1}}$${\displaystyle t_{1}}$${\displaystyle t_{2}}$${\displaystyle t_{1}}$${\displaystyle {\text{rank}}(t_{1})}$${\displaystyle t_{2}}$${\displaystyle {\text{rank}}(t_{1})}$${\displaystyle V(t_{1})}$${\displaystyle V(t_{1})}$${\displaystyle {\text{V-RANK-BOUND}}}$${\displaystyle {\text{V-SIZE-BOUND}}}$${\displaystyle t_{1}}$${\displaystyle \alpha }$

Ziel dieser Transformation ist es, die Gesamtzahl potenzieller Verstöße zu reduzieren, also zu verringern . ${\displaystyle \left|\bigcup _{x\in T_{1}\cup T_{2}}V(x)\cup W(x)\right|}$

Wir gehen davon aus, dass zwei potenzielle Verstöße gleichen Ranges vorliegen . Dann ergeben sich mehrere Fälle: ${\displaystyle x_{1}}$${\displaystyle x_{2}}$${\displaystyle k}$

1. Falls sich einer der Knoten als nicht verletzt herausstellt, entfernen wir ihn einfach aus der entsprechenden Verletzungsmenge.
2. Andernfalls stellen beide Knoten Verletzungen dar. Aufgrund von wissen wir, dass sowohl als auch mindestens einen Bruder haben. Dann gilt: ${\displaystyle {\text{ARITY-BOUND}}}$${\displaystyle x_{1}}$${\displaystyle x_{2}}$
   1. Wenn und keine Brüder sind, können wir ohne Beschränkung der Allgemeinheit annehmen, dass , und dann können wir die Teilbäume mit Wurzel und vertauschen . Die Anzahl der Verletzungen kann sich bei diesem Tausch nur verringern.${\displaystyle x_{1}}$${\displaystyle x_{2}}$${\displaystyle {\text{parent}}(x_{1})\leqslant {\text{parent}}(x_{2})}$${\displaystyle x_{1}}$${\displaystyle x_{2}}$
   2. Ansonsten sind und Brüder eines Knotens, den wir nennen werden . ${\displaystyle x_{1}}$${\displaystyle x_{2}}$${\displaystyle y}$
      1. Falls es mehr als einen Bruder vom Rang gibt , können wir diesen einfach abschneiden und ihn zu einem nicht verletzenden Knoten machen, wie im vorherigen Unterabschnitt beschrieben.${\displaystyle x_{1}}$${\displaystyle k}$${\displaystyle x_{1}}$${\displaystyle t_{1}}$
      2. Ansonsten sind sie die einzigen Kinder vom Rang von .. ${\displaystyle x_{1}}$${\displaystyle x_{2}}$${\displaystyle k}$${\displaystyle y}$
         1. Falls ja , können wir sowohl den Knoten als auch den Knoten aus dem Netzwerk entfernen und sie, wie im vorherigen Unterabschnitt beschrieben, zu nicht verletzenden Knoten des Netzwerks machen.${\displaystyle {\text{rank}}(y)>k+1}$${\displaystyle x_{1}}$${\displaystyle x_{2}}$${\displaystyle y}$${\displaystyle t_{1}}$
         2. Andernfalls schneiden wir ab. Der neue Rang von ist dann eins plus der Rang seines linken Sohnes. Wir ersetzen durch einen Sohn von Rang , der wie im vorherigen Unterabschnitt beschrieben abgeschnitten werden kann. Falls der Ersatz für ein verletzender Knoten vom Rang wird , fügen wir ihn zu hinzu . Schließlich erzeugen wir neue Söhne von wie oben beschrieben.${\displaystyle {\text{rank}}(y)=k+1}$${\displaystyle x_{1},x_{2}{\text{ and }}y}$${\displaystyle y}$${\displaystyle y}$${\displaystyle t_{1}}$${\displaystyle k+1}$${\displaystyle y}$${\displaystyle k+1}$${\displaystyle W(t_{1})}$${\displaystyle x_{1},x_{2}{\text{ and }}y}$${\displaystyle t_{1}}$

Die einzigen Verletzungsmengen, denen wir Verletzungen hinzufügen, sind und . Wie oben beschrieben, werden die Invarianten dieser Mengen mithilfe von Leitsätzen aufrechterhalten. Wenn wir eine Verletzung zu hinzufügen, ergeben sich zwei Fälle: ${\displaystyle V(t_{1})}$${\displaystyle W(t_{1})}$${\displaystyle W(t_{1})}$

1. Wenn genau 6 Verstöße gegen den vorgegebenen Rang vorliegen und es mindestens zwei verletzende Knoten gibt, die keine Söhne von sind , wenden wir die im Leitfaden angegebenen Operationen an.${\displaystyle t_{2}}$${\displaystyle {\text{REDUCE}}}$
2. Wenn mehr als vier Verstöße vorliegen, die Unterpunkte von sind , werden die zusätzlichen Verstöße entfernt und unten verlinkt . Dadurch wird der durch diese Knoten verursachte Verstoß beseitigt, ohne die Anleitung zu beeinträchtigen, die die Unterpunkte von verwaltet .${\displaystyle t_{2}}$${\displaystyle t_{1}}$${\displaystyle t_{2}}$

Bei jeder Prioritätswarteschlangenoperation erhöhen wir den Rang von um mindestens eins, indem wir eine konstante Anzahl von Söhnen von nach verschieben (vorausgesetzt, dass ). Durch die Erhöhung des Rangs von können wir Verletzungen zu hinzufügen, ohne die Invarianten zu beeinträchtigen. Falls und , können wir die größten Söhne von abschneiden , sie mit verbinden und dann einen Sohn von erstellen . Dies erfüllt alle Invarianten. Andernfalls schneiden wir einen Sohn von mit Rang ab , trennen diesen Sohn und fügen die resultierenden Bäume zu hinzu . Falls , wissen wir, dass der Knoten mit dem größten Rang ist, und daher können keine großen Verletzungen erzeugt werden. ${\displaystyle t_{1}}$${\displaystyle t_{2}}$${\displaystyle t_{1}}$${\displaystyle T_{2}\neq \emptyset }$${\displaystyle t_{1}}$${\displaystyle V(t_{1})}$${\displaystyle T_{2}\neq \emptyset }$${\displaystyle {\text{rank}}(t_{2})\leqslant {\text{rank}}(t_{1})+2}$${\displaystyle t_{2}}$${\displaystyle t_{1}}$${\displaystyle t_{2}}$${\displaystyle t_{1}}$${\displaystyle t_{2}}$${\displaystyle {\text{rank}}(t_{1})+2}$${\displaystyle t_{1}}$${\displaystyle T_{2}=\emptyset }$${\displaystyle t_{1}}$

${\displaystyle {\text{MakeQueue}}()}$Gibt einfach ein Paar leerer Bäume zurück.

${\displaystyle {\text{FindMin}}(Q)}$Rückgabewerte . ${\displaystyle t_{1}}$

${\displaystyle {\text{Insert}}(Q,e)}$ist nur ein Spezialfall von , wobei es sich um eine Warteschlange handelt, die nur und enthält . ${\displaystyle {\text{Meld}}(Q_{1},Q_{2})}$${\displaystyle Q_{2}}$${\displaystyle e}$${\displaystyle Q_{1}=Q}$

${\displaystyle {\text{Meld}}(Q_{1},Q_{2})}$Es werden vier Bäume verwendet (zwei für jede Warteschlange). Der Baum mit der kleinsten Wurzel wird zum neuen Baum. Ist dieser Baum auch der Baum mit dem höchsten Rang, können alle anderen Bäume wie zuvor beschrieben hinzugefügt werden. In diesem Fall entstehen keine Knoten mit Fehlern, daher werden keine Transformationen an diesen Knoten vorgenommen. Andernfalls wird der Baum mit dem höchsten Rang zum neuen Baum, und die anderen Bäume werden wie im Abschnitt „Verwalten der Kinder einer Wurzel“ beschrieben hinzugefügt. Haben einige Bäume den gleichen Rang wie der neue Baum , können sie vor dem Hinzufügen getrennt werden. Die entstehenden Fehler werden wie im Abschnitt „Vermeiden zu vieler Fehler“ beschrieben behandelt. ${\displaystyle T_{1}}$${\displaystyle T_{2}}$${\displaystyle T_{2}}$

${\displaystyle {\text{DecreaseKey}}(Q,e,e')}$wird durch das Element ersetzt . Falls , werden die beiden Knoten vertauscht, andernfalls wird die potenzielle neue Verletzung wie im Abschnitt „Vermeidung zu vieler Verletzungen“ erläutert behandelt. ${\displaystyle e}$${\displaystyle e'}$${\displaystyle e'\leqslant e}$${\displaystyle e'<t_{1}}$

${\displaystyle {\text{DeleteMin}}(Q)}$Die Laufzeit im ungünstigsten Fall darf maximal sein . Zuerst leeren wir den Baum vollständig , indem wir alle Söhne von in verschieben und anschließend einen Sohn vom Rang 0 von erstellen . Dann wird gelöscht, sodass maximal unabhängige Bäume übrig bleiben. Das neue Minimum wird gefunden, indem die Verletzungsmengen der alten Wurzel und alle Wurzeln der neuen Bäume betrachtet werden. Ist das minimale Element keine Wurzel, kann eine Wurzel aus einem Baum gleichen Rangs mit ihr vertauscht werden. Dadurch entsteht maximal eine Verletzung. Anschließend werden die unabhängigen Bäume durch Verknüpfungs- und Entkopplungsoperationen zu Söhnen des neuen minimalen Elements gemacht. Dies stellt die Invarianten und wieder her . Durch Zusammenführen der und Mengen der neuen Wurzel mit den und Mengen der alten Wurzel erhalten wir eine neue Verletzungsmenge der Größe . Durch maximal verletzungsreduzierende Transformationen können wir die Verletzungsmenge so anpassen, dass sie maximal ein Element jedes Rangs enthält. Diese Menge ist unsere neue und leere Menge. Dadurch werden die Invarianten wiederhergestellt. Außerdem muss ein neuer Guide für die neue Wurzel initialisiert werden . ${\displaystyle O(\log n)}$${\displaystyle T_{2}}$${\displaystyle t_{2}}$${\displaystyle t_{1}}$${\displaystyle t_{2}}$${\displaystyle t_{1}}$${\displaystyle t_{1}}$${\displaystyle O(\log n)}$${\displaystyle O(\log n)}$${\displaystyle {\text{RANK}}}$${\displaystyle {\text{ROOTS}}}$${\displaystyle V}$${\displaystyle W}$${\displaystyle V}$${\displaystyle W}$${\displaystyle O(\log n)}$${\displaystyle O(\log n)}$${\displaystyle W}$${\displaystyle V}$${\displaystyle {\text{SETS}}}$${\displaystyle t_{1}}$

Hierbei bezeichnet das kleinste mögliche Element. kann einfach durch Aufruf von gefolgt von implementiert werden . ${\displaystyle -\infty }$${\displaystyle {\text{Delete}}(Q,e)}$${\displaystyle {\text{DecreaseKey}}(Q,e,-\infty )}$${\displaystyle {\text{DeleteMin}}(Q)}$

In diesem Abschnitt fassen wir einige Implementierungsdetails für die Brodal-Queue-Datenstruktur zusammen.

In jedem Baum ist jeder Knoten ein Datensatz mit folgenden Feldern:

• Das dem Knoten zugeordnete Element (sein Wert),
• Der Rang des Knotens,
• Zeiger auf die linken und rechten Nachbarknoten,
• ein Zeiger auf den Vaterknoten,
• ein Zeiger auf den ganz links stehenden Sohn,
• Zeiger auf das erste Element des Knotens und Mengen,${\displaystyle V}$${\displaystyle W}$
• Zeiger auf das folgende und das vorherige Element in der Verletzungsmenge, zu der der Knoten gehört. Wenn dieser Knoten der erste Knoten der Verletzungsmenge ist oder zu der er gehört, zeigt der vorherige Zeiger auf .${\displaystyle V(x)}$${\displaystyle W(x)}$${\displaystyle x}$
• ein Array von Zeigern auf Söhne von Rang (mit ),${\displaystyle t_{1}}$${\displaystyle i}$${\displaystyle i\in \{0,\dots ,{\text{rank}}(t_{1})-1\}}$
• ein ähnliches Array für${\displaystyle t_{2}}$
• ein Array von Zeigern auf Knoten in vom Rang (mit ).${\displaystyle W(t_{1})}$${\displaystyle i}$${\displaystyle i\in \{0,\dots ,{\text{rank}}(t_{1})-1\}}$

Schließlich haben wir 5 Richtlinien: drei zur Aufrechterhaltung der oberen Schranken für und und zwei zur Aufrechterhaltung der unteren Schranken für und . ${\displaystyle {\text{arity}}_{i}(t_{1})}$${\displaystyle {\text{arity}}_{i}(t_{2})}$${\displaystyle w_{i}(t_{1})}$${\displaystyle {\text{arity}}_{i}(t_{1})}$${\displaystyle {\text{arity}}_{i}(t_{2})}$

Aufgrund der großen Anzahl an Zeigern und Mengen, die verwaltet werden müssen, ist die Brodal-Warteschlange extrem schwer zu implementieren. Daher lässt sie sich am besten als rein theoretisches Objekt zur Reduzierung der Zeitkomplexität von Algorithmen wie dem Dijkstra-Algorithmus beschreiben . Die Brodal-Warteschlange wurde jedoch in Scala implementiert (das GitHub- Repository ist hier zu finden: https://github.com/ruippeixotog/functional-brodal-queues ). In seiner Veröffentlichung erwähnt Gerth Stølting Brodal: „Eine wichtige Aufgabe für die weitere Arbeit ist die Vereinfachung der Konstruktion, um sie in der Praxis anwendbar zu machen.“ ^{[ 3 ]}

Hier sind die Zeitkomplexitäten ^{[ 4 ]} verschiedener Heap-Datenstrukturen aufgeführt. Die Abkürzung „ am.“ bedeutet, dass die angegebene Komplexität amortisiert ist; andernfalls handelt es sich um die Worst-Case-Komplexität. Zur Bedeutung von „ O ( f )“ und „ Θ ( f )“ siehe Big-O-Notation . Die Operationsnamen setzen einen Min-Heap voraus.

Gerth Stølting Brodal ist Professor an der Universität Aarhus , Dänemark . ^{[ 20 ]} Er ist vor allem für die Brodal-Warteschlange bekannt.