AuK/Prioritätswarteschlangen SS12
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>Java</language>
=Einführung=
Eine Prioritätswarteschlange ist eine spezielle abstrakte Datenstuktur und, wie der Name bereits vermuten lässt, eine erweiterte Variante einer Warteschlange(queue). Die Elemente der Warteschlange haben Schlüssel, die ihre Priorität bestimmen.
Prioritätswarteschlangen lassen sich mit verschiedenen Datenstrukturen implementieren. Hier werden sie anhand von Heaps vorgestellt.
=Amortisierte Laufzeitanalyse=
Eine amortisierte Laufzeitanalyse betrachtet die mittlere Laufzeit pro Operation über eine Sequenz von Operationen.
Im Gegensatz zur bisher verwendeten Laufzeitanalyse wird also nicht nur der Worst Case betrachtet. Es ist möglich, dass dieser zwar eine sehr schlechte Laufzeit hat, aber nur wenige Male im Ablauf des Algorithmus vorkommt. Alle anderen Fälle können dagegen sehr günstig sein. Durch diese Alternative Betrachtung kommt es oft zu einer besseren oberen Schranke für die Laufzeit.
Es gibt drei unterschiedliche Methoden: <br>
'''Aggregat-Methode'''
Zeigt, dass eine Sequenz von n (beliebigen) Operationen für alle n im worst case Zeit T(n) benötigt.
Damit sind die mittleren (amortisierten) Kosten pro Operation T(n)/n.
Diese amortisierten Kosten gelten für jede Operation, auch wenn in der Sequenz verschiedene Operationstypen auftreten.
'''Account-Methode'''
Verschiedenen Operationen werden verschiedene Kosten zugeordnet, diese können auch größer oder kleiner als die tatsächlichen Kosten sein. Übersteigen die amortisierten Kosten die tatsächlichen, wird die Differenz speziellen Objekten in der Datenstruktur als Kredit zugewiesen. Dieser kann später verwendet werden, wenn die tatsächlichen Kosten höher als die amortisierten sind.
Dabei ist zu beachten, dass der Gesamtkredit niemals negativ sein darf.
'''Potenzial-Methode'''
Verschiedenen Operationen werden verschiedene Kosten zugeordnet, diese können auch größer oder kleiner als die tatsächlichen Kosten sein. Hier wird die Differenz zwischen amortisierten und tatsächlichen Kosten der Datenstruktur als Ganzes in Form eines Potenzials zur Verfügung gestellt. Dieses wird bei Operationen benötigt, deren Kosten höher sind als die amortisierten.
Eine Potentialfunktion bildet jede Datenstruktur auf eine reelle Zahl ab, die dem Potenzial entspricht. Diese Potentialfunktion ist zu Beginn immer gleich 0, danach nie negativ.
=Normale Warteschlangen=
[[Bild:HansV2_Queue.gif|gerahmt|Prozess des hinzufügens und herausnehmens von Elementen aus einer Warteschlange]]
Normale Warteschlangen funktionieren nach dem FiFo-Prinzip (First in, first out).
Es existieren verschiedene Formen der normalen Warteschlangen, z.B. dynamisch erweiterbare oder
Warteschlangen mit fester Größe.
Anwendung findet die normale Warteschlange vor allem bei verteilten Systemen bei bei der Synchronisation von Prozessen/Threads.
Dies lässt sich am Beispiel der Warteschlange bei Druckaufträgen vorstellen.
Wenn ein Druckauftrag gesendet wurde, der Drucker jedoch bereits in benutzung ist, so wird der Druckauftrag in eine Warteschlange gesteckt.
So kann der Drucker die anstehenden Aufträge seriell abarbeiten, ohne, dass der Nutzer warten muss bis der Drucker wieder frei ist.
Eine gute Analogie, um die normalen Warteschlangen zu beschreiben ist "Wer zuerst kommt mahlt zuerst" (oder in unserem Beispiel "druckt zuerst").
==Benötigte Methoden==
Um mit normalen Warteschlangen arbeiten zu können benötigt man mindestens zwei Methoden:
*Enqueue: Zum Hinzufügen neuer Elemente.
*Dequeue: Zum Herausnehmen des "ersten" Elements.
<popup name="Klassen-Definitionen">
<code id="35435435436546546">
public Object Queue(){
private Object[] elements = new Object[0];
public void enqueue(Object element){
int length = elements.length;
Object[] newElements = new Object[length+1];
for(int i=0; i<= length-1; i++){
newElements[i] = elements[i];
}
newElements[length] = element;
elements = newElements;
}
public Object dequeue(){
int length = elements.length;
Object firstElement = elements[0];
Object[] newElements = new Object[length-1];
for(int i=0; i< length-1; i++){
newElements[i] = elements[i+1];
}
elements = newElements;
return firstElement;
}
public void showElements(){
String output = "[";
for(Object element : elements){
output += element+", ";
}
System.out.println(output.substring(0,output.length()-2)+"]");
}
return this;
}
</code>
</popup>
<run id="35435435436546546">
queue= Queue();
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
queue.showElements();
System.out.println(queue.dequeue());
System.out.println(queue.dequeue());
System.out.println(queue.dequeue());
</run>
=Binäre Heaps=
Zum besseren Verständis beim Umgang mit Heaps wird der Heapsort Algorithmus erläutert.
Ein binärer Heap kann als ein fast vollständiger binärer Baum angesehen werden. Jeder Knoten entspricht dabei einem Element des Feldes.
Die niedrigste Ebene des Baumes ist von links her bis zu einem bestimmten Punkt, der Rest vollständig gefüllt.
Ist A ein Feld, dass einen Heap repräsentiert, dann hat es zwei Eigenschaften: ''länge''[A], die Anzahl der Elemente des Feldes, und ''heap-größe''[A], die Anzahl der Elemente im Heap.
Es ist also kein Element hinter A[''heap-größe''(A)] mit ''heap-größe''[A] <math>\leq</math> ''länge''[A] ein Element des Heaps. Die Wurzel des Baumes ist A[1].
Bei gegebenem Index $i$ lassen sich die Indizes des Vaters ''Vater''($i$) und die des rechten und linken Kindes ''Right''($i$), bzw. ''Left''($i$) berechnen.
Vater($i$)
<math>\lfloor</math> '''return'''' i/2 <math>\rfloor</math>
Right($i$)
'''return''' 2i
Left($i$)
'''return''' 2i+1
Die Höhe eines Knoten ist als die Anzahl der Kanten des längsten einfachen absteigenden Pfades zu einem Blatt definiert.
Die Höhe des Heaps ist die Höhe seiner Wurzel.
Ein Heap mit $n$ Elementen hat die Höhe <math>\theta</math>(lg n), da er auf einem vollständigen binären Baum basiert.
==Arten binärer Heaps==
Es gibt zwei Arten binärer Heaps: '''''Max-Heaps''''' und '''''Min-Heaps'''''. Beide erfüllen eine spezifische '''''Heap-Eigenschaft'''''.
Die '''''Max-Heap-Eigenschaft''''' besteht darin, dass für jeden Knoten $i$ außer der Wurzel gilt:
A[Vater($i$)] <math>\geq</math> A[$i$], d.h. der Wert eines Knotens ist stets höchstens so groß, wie der seines Vaters. In einem '''''Max-Heap''''' liegt das größte Element also in der Wurzel.
Ein '''''Min-Heap''''' ist entgegengesetzt aufgabaut. Hier gilt:
A[Vater($i$)] <math>\leq</math> A[$i$].
Hier liegt in der Wurzel das kleinste Element.
Für Heapsort werden Max-Heaps verwendet, für Prioritätswarteschlangen Min-Heaps.
==Grundlegende Operationen==
===Max-Heapify===
Sorgt für die Aufrechterhaltung der Heap-Eigenschaft.
Erhält ein Feld A und einen Index i. Es wird angenommen, dass die Bäume, die von Left(i) und Right(i) ausgehen die Max-Heap-Eigenschaft erfüllen,
A[i] dagegen kann kleiner als seine Kinder sein, was die Heap-Eigenschaft verletzen würde.
Max-Heapify lässt den Wert von A[i] im Heap nach unten sinken, sodass der von i ausgehende Teilbaum zu einem Max-Heap wird.
Max-Heapify(A,i)
l<math>\leftarrow</math>Left(i)
r<math>\leftarrow</math>Right(i)
'''if''' l <math>\leq</math> heap-größe[A] und A[l] > A[i]
'''then''' maximum <math>\leftarrow</math> l
'''else''' maximum <math>\leftarrow</math> i
'''if''' r <math>\leq</math> heap-größe[A] und A[r] > A[maximum]
then maximum <math>\leftarrow</math>r
'''if''' maximum <math>\neq</math> i
'''then''' vertausche A[i] <math>\leftrightarrow</math> A[maximum]
Max-Heapify(A,maximum)
<popup name="Klassen-Definitionen">
<code id="xgjsdtzgndrtz">
public Object Heap(){
public void maxHeapify(int[] heap, int position){
int leftPosition = (position+1)*2-1;
int rightPosition = leftPosition+1;
int node = heap[position];
int maximum = 0;
int heapSize = heapSize(heap);
if(leftPosition <= heapSize && heap[leftPosition] > node){
maximum = leftPosition;
}else{
maximum = position;
}
if(rightPosition <= heapSize && heap[rightPosition] > heap[maximum] ){
maximum = rightPosition;
}
if(maximum != position){
System.out.println("switching: "+heap[maximum]+" with: "+node);
heap[position] = heap[maximum];
heap[maximum] = node;
maxHeapify(heap, maximum);
}
}
private int heapSize(int[] heap){
int maxHeapSize = heap.length-1;
for(int i = heap.length-1;i>= 0; i--){
if(heap[i]==0){
maxHeapSize--;
}else{
break;
}
}
return maxHeapSize;
}
public void print(int[] arr){
for(int element : arr){
System.out.print(element + " ");
}
System.out.println("");
}
return this;
}
</code>
</popup>
<run id="xgjsdtzgndrtz">
heapO = Heap();
int[] heap = {1,5,3,2,4};
heapO.maxHeapify(heap, 0);
heapO.print(heap);
</run>
Abbildung
====Laufzeit====
Die Laufzeit setzt sich zusammen aus <math>\Theta(1)</math> um die Beziehungen zwischen ''A[i]'', ''A[Left(i)]'' und ''A[Right(i)]'' zu bestimmen, sowie der Zeit für
die Ausführung von Max-Heapify auf einen von ''i'' ausgehenden Teilbaum. Die von den Kindern ausgehenden Teilbäume haben höchstens die Größe <math>\frac{2n}{3}</math>.
Der schlechteste Fall tritt ein, wenn die letzte Ebene des Baumes exakt halb gefüllt ist.
Die Rekursionsgleichung <math>T(n) \leq T(\frac{2n}{3})+\Theta(1)</math> beschreibt die Laufzeit von Max-Heapify.
Nach dem Mastertheorem ist die Lösung <math>T(n)=O(lg (n))</math>. Die Laufzeit auf einen Knoten der Position ''h'' kann auch mit <math>O(h)</math> angegeben werden.
Build-Max-Heap erzeugt einen Max-Heap aus einem ungeordneten Feld <math>O(n)</math>
===Build-Heap===
Um ein Feld A[1..n] mit n=länge[A] in einen Max-Heap zu überführen kann die Prozedur Max-Heapify bottom-up angewendet werden.
Alle Elemente im Teilfeld A[(<math>\lfloor</math> <math>\frac{n}{2}</math> <math>\rfloor +1</math>)..n] sind Blätter des Baumes, daher sind sie zu Beginn einelementige Heaps.
Build-Max-Heap durchläuft alle übrigen Knoten und führt dort Max-Heapify aus.
Build-Max-Heap(A)
heap-größe[A] <math>\leftarrow</math> länge[A]
'''for''' i <math>\leftarrow \lfloor</math>länge[A]/2<math> \rfloor </math> '''downto''' 1
'''do''' Max-Heapify(A,i)
<popup name="Klassen-Definitionen">
<code id="6516516516s">
public Object Heap(){
public void buildMaxHeap(int[] heapCandidate){
int heapLength = heapCandidate.length-1;
for(int i=(int) (Math.floor(heapLength)/2);i>=0;i--){
System.out.println("checking position: "+i+" ("+heapCandidate[i]+")");
maxHeapify(heapCandidate,i);
print(heapCandidate);
System.out.println("---------");
}
}
public void maxHeapify(int[] heap, int position){
int leftPosition = (position+1)*2-1;
int rightPosition = leftPosition+1;
int node = heap[position];
int maximum = 0;
int heapSize = heapSize(heap);
if(leftPosition <= heapSize && heap[leftPosition] > node){
maximum = leftPosition;
}else{
maximum = position;
}
if(rightPosition <= heapSize && heap[rightPosition] > heap[maximum] ){
maximum = rightPosition;
}
if(maximum != position){
System.out.println("switching: "+heap[maximum]+" with: "+node);
heap[position] = heap[maximum];
heap[maximum] = node;
maxHeapify(heap, maximum);
}
}
private int heapSize(int[] heap){
int maxHeapSize = heap.length-1;
for(int i = heap.length-1;i>= 0; i--){
if(heap[i]==0){
maxHeapSize--;
}else{
break;
}
}
return maxHeapSize;
}
public void print(int[] arr){
for(int element : arr){
System.out.print(element + " ");
}
System.out.println("");
}
return this;
}
</code>
</popup>
<run id="6516516516s">
heapO = Heap();
int[] heap = {1,2,3,5,4,7,8,9};
heapO.buildMaxHeap(heap);
heapO.print(heap);
</run>
Eine obere Schranke für die Laufzeit von Build-Max-Heap lässt sich grob abschätzen. Max-Heapify kostet Zeit O(lg n) und wird O(n) mal aufgerufen.
Die dadruch abgeschätzte Schranke O(n lg n) ist allerdings nicht sehr genau.
Um eine schärfere Schranke herzuleiten nutzt man aus, dass die Laufzeit von Max-Heapify mit der Höhe des Knotens variiert und dass die Höhe meißtens klein ist.
Ein n-elementiger Heap hat die Höhe <math> \lfloor lg n \rfloor </math> und es gibt höchstens <math>\lceil n/2^{h+1} \rceil </math> Knoten mit Höhe h.
Da die Zeit von Max-Heapify auf einen Knoten der Höhe h O(h) ist, kann für Build-Max-Heap die obere Schranke
<math>\sum\limits_{h=0}^{\lfloor lg n \rfloor} \lceil \frac{n}{2^{h+1}}\rceil O(h) = O (n \sum\limits_{h=0}^{\lfloor lg n \rfloor} \frac{h}{2^{h}} </math>
angegeben werden.
Sei x=1/2, dann ist
<math>\sum\limits_{h=0}^{\infty}\frac{h}{2^{h}} = \frac{1/2}{(1-1/2)^{2}}
=2</math>
Damit kann man die Laufzeit durch <math>O (n \sum\limits_{h=0}^{\lfloor lg n \rfloor} \frac{h}{2^{h}} = O(\sum\limits_{h=0}^{\infty}\frac{h}{2^{h}} = \frac{1/2}{(1-1/2)^{2}})
=O(n)</math> abschätzen.
==Übungsaufgaben==
*Mastertheorem Anwendung für die Rekursionsgleichung von Max-Heapify (<math>T(n) \leq T(\frac{2n}{3})+\Theta(1)</math>)
Allgemeine Form des Mastertheorems:<br/>
<math>T(n) = a \sdot T(\textstyle \frac{n}{b}) + f(n)</math><br/><br/>
<popup name="a, b, f(n)">
<math>a = 1</math><br/><br/>
<math>b = \frac{3}{2}</math><br/><br/>
<math>f(n) = 1</math><br/><br/>
</popup>
<popup name="Fall 2">
<math>T(n) = O(n^{\log_b a}*lg(n))</math><br/><br/>
<math>\log_b a = \log_\frac{3}{2} 1 = 0</math><br/><br/>
<math>T(n) = O(n^0*lg(n))</math><br/><br/>
<math>T(n) = O(lg(n))</math><br/><br/>
</popup>
<br/>
*Was ist die maximale und minimale Anzahl von Elementen in einem Heap der Höhe h?
<popup name="Minimal">
<math>1</math>
</popup>
<popup name="Maximal">
<math>2^{h+1}-1</math>
</popup>
<br/>
*In einem max heap, wo befindet sich das kleinste element, wenn alle paarweise verschieden sind?
<popup name="Lösung">
In einem der Blätter.
</popup>
<br/>
*Ist [5,4,1,3,2] ein max heap?
<popup name="Lösung">
ja
</popup>
<br/>
*Was macht Max-Heapify(A,i), wenn A[i] größer als seine Kinder ist
<popup name="Lösung">
Max-Heapify macht in diesem Fall nichts.
</popup>
<br/>
=Prioritätswarteschlangen=
Wie bei Heaps gibt es auch hier zwei Varianten '''''Max-Prioritätswarteschlangen''''' und '''''Min-Prioritätswarteschlangen'''''. Im folgenden werden Min-Prioritätswarteschlangen
verwendet.
;Prioritätswarteschlange
:Eine Prioritätswarteschlange ist eine Datenstruktur für die Speicherung einer Menge S, deren Elementen jeweils ein Wert zugeordnet ist, den man als Schlüssel bezeichnet.
:
==Grundoperationen==
===decrease-key(S,x,k)===
Verringert den Wert des Schlüssels von Element x auf den neuen Wert k. Da so die Heap-Eigenschaft verletzt werden kann, dürchläuft die Prozedur
anschließend vom Knoten i beginnend den Heap bis zur Wurzel um die richtige Position zu finden.
decrease-key(S,i,k)
if k > A[i]
then return "neuer Schlüssel ist größer als der aktuelle Schlüssel"
A[i]<math>\leftarrow</math>k
while i > 1 und A[Vater(i)] > A[i]
do A[i]<math>\leftrightarrow</math>A[Vater(i)]
i<math>\leftarrow</math>Vater(i)
Laufzeit auf einem Heap mit n Elementen ist O(lg n), da der Pfad vom Knoten i bis zur Wurzel die Länge O(lg n) hat.
===Insert(S,x)===
Fügt das Element x in die Menge S ein. Die Operation kann als S <math>\leftarrow</math> S <math>\bigcup</math> {x} geschrieben werden.
Zunächst wird der Heap erweitert, indem ein neues Blatt mit dem Platzhalter Schlüssel "X" eingefügt wird. Anschließend wird mittels Heap-Decrease-Key der
korrekte Schlüssel eingefügt und gegebenenfalls die Heap-Eigenschaft wiederhergestellt,
Insert(S,x)
heap-größe[A]<math>\leftarrow</math>heap-größe[A]+1
A[heap-größe[A]]<math>\leftarrow</math>X
Heap-Decrease-Key(A,heap-größe[A],x)
Laufzeit auf einem Heap mit n Elementen ist O(lg n).
===Minimum(S)===
gibt das Element mit dem kleinsten Schlüssel zurück
Minimum(s)
return A[1]
Laufzeit trivial <math>\theta(1)</math>.
===Extract-Min(S)===
entfernt das kleinste Element und gibt es zurück
Extract-Min(S)
if heap-größe[S]<1
then return "Heap Unterlauf"
min<math>\leftarrow</math>S[1]
S[1]<math>\leftarrow</math>S[heap-größe(S)]
heap-größe(S)<math>\leftarrow</math>heap-größe(S)-1
Min-Heapify(S,1)
return min
Die Laufzeit von Extract-Min(S) ist O(lg n), da zusätzlich zu Min-Heapify nur eine konstante Zeit kommt.
Übung
Extract-Min([Heap])
Insert(H,10) A=[]
==Adressierbare Prioritätswarteschlangen==
Die Struktur binärer Heaps ist zu unflexibel für die Implementierung adressierbarer Prioritätswarteschlangen, daher werden hierfür andere Formen von Heaps verwendet.
Diese versprechen schnellere Laufzeiten für insert, decreaseKey, remove und merge.
Der Einzelne binäre Baum wird ersetzt durch eine Sammlung von Bäumen (einem sogenannten Wald) mit willkürlicher Struktur.
Dabei erfüllen die einzelnen Bäume natürlich immernoch die Heap-Eigenschaft.
Weiterhin wird ein Zeiger auf jedes Heap Element im Speicher behalten. Dabei zeigt minPtr auf das kleinste element.
Der Wald wird mit drei Operationen verwaltet: Einen neuen Baum hinzufügen, zwei Bäume verbinden und einen Teilbaum abschneiden.
insert fügt einen einelementigen Baum hinzu O(1)
delete min löscht kleinstes element -> kinder werden wurzeln, neues minimum suchen, rebalancing -> schlüssel zur effizienz
decreaseKey(h,k) Schlüsselwerte bei position h auf k reduziert, kann heap eigenschaft verletzen ->
teilbaum mit wurzel h abschneiden
remove decreasen bis kleinstes element, delete min
merge union von wurzeln, minPtr aktualisieren (kleinere wurzel)
Durch diese operationen können sehr schlecht struktuierte bäume entstehen, daher werden bei einigen varianten zusätzliches rebalancing
===Binominal Bäume===
Im Gegensatz zu binären heaps können binomial Heaps effizient vereinigt werden.
Binomial-Heaps unterstützen die Operationen insert, remove, extractMin, decreaseKey, merge
Alle Operationen lassen sich mit einer Worst-Case-Laufzeit von O(log n) implementieren.
Binomial-Heaps bestehen aus einer Liste von Binomial-Bäumen verschiedener Ordnung. Diese erfüllen alle die Heap-Eigenschaft.
Die Bäume sind dabei rekursiv definiert.
Ein Binomial-Baum der Ordnung 0 besteht aus einem einzelnen Knoten.
Ein Binomial-Baum der Ordnung k besitzt eine Wurzel mit Grad k deren Kinder genau die Ordnung k-1, k-2, ..., 0 (in dieser Reihenfolge) besitzen.
Damit lässt sich ein Binomial-Baum der Ordnung k leicht aus zwei Binomial-Bäumen der Ordnung k-1 erstellen. Dabei wird einer der beiden Bäume
zum am weitesten links stehenden Kind des anderen gemacht. Daraus lässt sich ableiten, dass ein Binomial-Baum der Ordnung k genau 2^k Knoten und Höhe k hat.
Operationen
merge
Die Verschmelzung zweier Heaps ist die zentrale Operation bei binomial-Heaps, da sie bei allen anderen Operationen aufgerufen wird.
Dazu werden simultan die Listen der beiden Heaps beginnend bei den Bäumen niedrigster Ordnung durchlaufen. In einer speziellen Variablen wird – ähnlich der bitweisen Addition – ggf. ein Übertrag (in Form eines Baumes) festgehalten. Anfangs ist dieser Übertrag leer.
Sei nun x die höchste Binärstelle von n_1+n_2 verschieden von 0, das heißt x=\log_2(n_1+n_2+1)-1. Zu jeder natürlichen Zahl k mit 0\leq k\leq x wird nun in aufsteigender Reihenfolge die Anzahl der Bäume mit Ordnung k in beiden Heaps und in der Übertragsvariablen betrachtet. Ist diese
0, so passiert nichts.
1, so wird der entsprechende Baum in den neuen Heap übernommen und der Übertrag ggf. geleert.
2, so wird der Baum, dessen Schlüssel an der Wurzel größer ist, zum am weitesten links stehenden Kind des anderen Baumes gemacht und der so entstehende Baum der Ordnung k+1 als Übertrag behalten.
3, so wird der Baum aus dem Übertrag in den neuen Heap übernommen und von den beiden Bäumen in den Heaps wird der Baum, dessen Schlüssel an der Wurzel größer ist zum am weitesten links stehenden Kind des anderen Baumes gemacht und der so entstehende Baum der Ordnung k+1 als Übertrag behalten.
Jeder dieser Schritte lässt sich in konstanter Zeit durchführen. Da maximal \log_2(n_1+n_2+1) derartige Schritte getätigt werden, benötigt die Operation im schlimmsten Fall nur logarithmisch viel Zeit.
remove
Neben merge ist das Entfernen eines Elementes (remove), die anspruchsvollste Operation. Sei X das zu entfernende Element, seine Ordnung x und T der Binomial-Baum, der dieses Element enthält und dessen Ordnung k beträgt. Ausgehend von X muss der Binomial-Baum, der das Element enthält, geeignet in kleinere Binomial-Bäume aufgespalten werden. Dieses Aufspalten des Baumes geschieht am einfachsten mit einer rekursiven Funktion split, der als Argument ein Knoten im Baum übergeben wird. Anfangs ist X selbst das Argument. Sofern das übergebene Argument einen Elternknoten besitzt, ruft sich die Funktion zuerst selbst mit diesem als Argument auf und entfernt anschließend solange das am weitesten links stehende Kind des Vaters – also das Kind mit höchster Ordnung – bis das Argument selbst aus dem Baum entfernt wurde.
Da das Entfernen des am weitesten links stehenden Elementes gerade die umgekehrte Operation zum oben dargestellten rekursiven Aufbau der Binomial-Bäume darstellt, sind die so abgespaltenen Bäume und der Rest weiterhin Binomial-Bäume. Ferner ist X nun Wurzel eines Baumes und es lässt sich zeigen, dass der ursprüngliche Baum nun in genau 2 Binomial-Bäume der Ordnung x sowie in jeweils einen Binomial-Baum der Ordnung x+1, x+2, ..., k-1 zerfallen ist. Werden nun noch in gleicher Weise alle Kinder von X entfernt, so ist X vollständig isoliert und kann problemlos gelöscht werden. Dabei entsteht aus den Kindern für jedes j in {0, ..., x-1} jeweils genau ein Binomial-Baum der Ordnung j. Insgesamt bleibt also für jedes j aus {0, ..., k-1} ein Binomial-Baum der Ordnung j übrig. Diese Bäume bilden zusammen wieder einen Binomial-Heap, der mittels merge mit dem Rest des Heaps verschmolzen werden kann.
Das Abspalten des am weitesten links stehenden Elementes ist in konstanter Zeit möglich. Da der ursprüngliche Baum genau k mal aufgespalten wird, der Binomial-Heap aber mindestens 2k Elemente enthält, benötigt diese Operation im Worst-Case nur logarithmisch viel Zeit. Da das anschließende merge selbst auch nur logarithmisch viel Zeit benötigt ist auch die Gesamtlaufzeit im schlimmsten Fall logarithmisch zur Anzahl der Elemente im Heap.
Weitere Operationen
Die übrigen Operationen gestalten sich nun sehr einfach.
Um ein neues Element einzufügen (insert), wird einfach ein neuer Heap erzeugt, der nur dieses eine Element enthält und dieser mittels merge mit dem eigentlichen Heap verschmolzen.
Um ein Element mit minimalem Schlüssel zu entnehmen (extractMin), braucht lediglich das Minimum der Wurzeln gefunden zu werden, indem die Liste der Wurzeln einmal durchlaufen wird und das gefundene Element mit remove entfernt und zurückgegeben wird.
Um den Schlüssel eines Elementes zu verändern (changeKey) wird dieses mit remove zunächst entfernt, dann dessen Schlüssel geändert und anschließend mit insert wieder eingefügt.
===Pairing-heaps===
paarungs heaps
schwächen fibonacci
Fibonacci Heaps haben zwei Schwächen. Ihre Implementierung ist sehr kompliziert und sie haben sich in der praxis als
weniger effizient erwiesen, als theoretisch schwächere Formen von Heaps. Dies ist darauf zurückzuführen, dass sie in der einfachsten
Variante Speicher für vier Zeiger pro Knoten benötigen. Im vergleich dazu werden sonst nur zwei bis drei Zeiger verwendet.
entwickelt um fibonacci heaps in theorie und praxis zu schlagen
komplette analyse felht bisher
Pairing Heaps sind eine selbstverwaltende Variante der binomialen Heaps.
Es wird angenommen, dass sie theoretisch genauso Effizient sind, wie Fibonacci Heaps. Dies wurde jedoch bisher nicht bewiesen.
Die beste Analyse im Orginalpaper liefert eine Zeit von O(log n) für jede Heap Operation
wichtigste operation ist delete min, da nur hier die heapsturktur gewartet wird.
andere operationen:
make heap(h) neuer leerer baum h
find min(h) return root
insert x,h) x wird einelementiger baum + linken mit h
meld(h1,h2) linken h1, h2
decrease key(i,x,h) subtrahiere i vom schlüssel von element x. wenn x nicht die wurzel ist: schneide kante, die x mit vater verbindet ab und linke di ebeiden bäume
delete(x,h) ist x die wurzel von h, delete min(h)
sonst kante, die x mit vater verbindet abschneiden, x baum delete min, linken
Die zugrunde liegende Datensturktur ist ein Binärbaum. Jeder Knoten hat einen linken Zeiger, der auf das erste Kind zeigt und einen rechten Zeiger,
der auf den nächstgrößeren Knoten zeigt.
Damit decrease key und delete effizient sind wird ein dritter Zeiger benötigt, der auf den Vaterknoten zeigt.
Dieser Zeiger kann eingespart werden, indem man einen Zeiger auf das linke Kind und einen auf den rechten Geschwisterknoten, bzw. den Elternknoten richtet.
Dies geschieht auf Kosten einen konstanten Faktors in der Laufzeit.
make heap, find min, insert, meld und drecrease key haben O(1) worst case
delete braucht O(1)+ delete min -> delete und delete min sind die einzigen, die in nicht konstanter zeit laufen
delete min in heap eigenschaft erfüllendem baum
wurzel löschen, entsteht eine gruppe heaps (erfüllen eigenschaft), linken der einzelnen bäume zu einem neuen
reihenfolge ist wichtig
wie man die kombination auch gestaltet, /theta(n) worst case grenze, da jeder n-knotige baum, speziell der mit wurzel und n-1 knoten
durch eine reihe von O(n) make tree, insetr und meld operationen aufgebaut werden kann
eine amortisierte laufzeit von O(log n) ist möglich
primitive variante: einen baum auswählen und die anderen einen nach dem anderen linken
benötigt /theta(n) zeit
schnellere variante
1. durchlauf bäume zu paaren linken
2. dl bäume mit einem ausgewählten linken
sind paare beim ersten durchlauf schlecht gewählt ist \theta(sqrt(n)) amortisierte zeit möglich
bild 6 zeigt, dass es möglich ist insert, gefolgt von delete min in omega srt n zeit, dabei wird heap sturktur wiederhergestellt
analyse liefert O(sgrt n) amortisierte obere schrnake -> besser als primitive lösung
obere schranke berechnen
\tbd s6 technik sleator
varianten optional ab s13
===Fibonacci-Heaps===
Ein Fibonacci-Heap besteht aus einer Liste von Bäumen mit geordneten Nachfolgern, deren Knoten Schlüssel und möglicherweise eine Markierung enthalten.
Der Schlüssel wird hierbei als Priorität gesehen. Wie bei allen anderen Heaps muss die Heap-Eigenschaft vorhanden sein.
Ein Fibonacci-Heap wird normalisiert genannt, wenn alle Bäume unterschiedliche Wurzelränge (Prioritäten) haben.
====Besonderheit====
Im Gegensatz zu anderen Heaps weisen die Fibonacci-Heaps eine besondere Struktur auf.
Diese Besonderheit war ebenfalls namensgebend.
Die Fibonacci-Folge
====Benötigte Methoden====
Fibonacci-Heaps unterstützen die Operationen:
*insert: Einfügen eines Elementes.
*remove: Entfernen eines Elemente.
*Min: Finden des Elements mit dem minimalen Schlüssel.
*extractMin: Rückgabe und Entfernen eines Elementes mit minimalem Schlüssel (In einem Min-Heap entspricht dies der höchsten Priorität).
*decreaseKey: Verringern des Schlüssels eines Elementes.
*merge: Verschmelzen zweier Heaps.
====Übungsaufgaben====