cards-deck: 100-199_university::111-120_theoretic_cs::111_algorithms_datastructures

Heaps | schnell geordneter Baum:

anchored to [[111.00_anchor]]

Motivation:

[!Definition] Heaps in ihrer Idee: Mit einem Heap beschreiben wir eine baumartige Datenstruktur, wobei jedes Element einen Key und Value hat/aufweist. Sie sind zur Verwaltung von Mengen mit einer angewandten [[math1_relationen#Definition totale Ordungsrelation def|Orgnungsrelation]]

Sie dienen als :: Kompromiss zwischen ungeordnetem Array und geordnetem Array ^1704708670537

• müssen nicht extra geordnet werden, somit weniger kostenaufwendig
• jedoch schnelle Suche möglich

Wir können Heaps in zwei Arten aufbauen :: Max-Heap ( groß nach klein) und Min-Heap (von klein nach groß) ^1704708670547

Grundlage:

Wenn wir einen Heap betrachten, dann möchten wir in diesem eine Menge $S$ speichern. Hierbei wird sie von klein nach groß geordnet!(dann ist es ein MIN-Heap) oder von groß nach klein(dann ist es ein MAX-Heap), #card

[!Tip] Ordnung in einem Min-Heap: Also wenn wir zwei Elemente betrachten $v$ und $u$, wobei $u$ die Mutter von $v$ ist, dann muss gelten: $S[u]\le S[v]$ also das Mutter-Element muss immer kleiner sein, als seine Abkömmlinge! Betrachten wir folgendes Beispiel $S=\{1,2,3,4,5,4,7,8\}$ Dann können wir es etwa so in einem MIN Heap anordnen: ![[Pasted image 20231029172851.png]] ^1704708670552

[!Definition] Max/Min-Heap property: #card Mit der Max/Min-Heap Property beschreiben wir die obige Regel, dass alle Knoten im Baum folgende Ordnung aufweisen: key(parent(v)) >= key(v) für max Heap oder key(parent(v)) <= key(v) ^1704708670558

Binary Heaps:

Heaps kann man mit einem $k$-Baum konstruieren, oder auch mit binary-Bäumen. Wir werden uns primär auf binäre Bäume beziehen, da sie grundsätzlich einige Vorteile haben. Folgend listen wir die Eigenschaften eines binary Heaps: #card

• jeder Knoten hat maximal 2 Kinder
• wir füllen erst eine gesamte Stufe, bis wir in die nächste übergehen. Wir füllen dabei von links nach rechts
• wir können diese Struktur einfach in einem Array darstellen
• Wir haben den Vorteil, dass wir individuell die Höhe und Tiefe des Baumes bestimmen bzw kontrollieren können ^1704708670564

Operationen:

Ferner haben Heaps bestimmte Operationen, die notwendig sind, um mit ihnen zu arbeiten:

Operationen:

• Insert(Value)
• IncreaseKey
• DecreaseKey
• ExtractMin

Heapify | Garantieren des Heaps:

Wir wissen, dass ein richtiger Heap in seiner Struktur so aufgebaut ist, dass jedes Kind eines Knotens streng größer/kleiner sein muss als er selbst. Durch diese Vergrößerung/Verkleinerung in die Tiefe befindet sich das kleinste/größte Element immer ganz oben. Wenn wir jetzt etwa das kleinste/größte Element entfernen, kann es sein, dass unser Heap in der Struktur nicht mehr richtig ist. Wie können wir dann wieder den Heap aufbauen? #card

[!Tip] Wiederherstellen des Heaps: Mit der Heapify Funktion stellen wir die geordnete Struktur des Heaps wieder her. Das setzen wir damit um, dass wir bei jedem Knoten schauen, ob die Kinder noch größer/kleiner sind, oder ob geswapped werden muss. ^1704708670569

Beweis der Richtigkeit:

Wir möchten folgend beweisen, dass diese Wiederherstellung korrekt ist. Dabei beziehen wir uns auf einen binary max heap . Folgend möchten wir mit $a$ die Key-Value am Index $i$ beschreiben. Ferner sind dann $b_1,b_2$ die Kinder von $i$. Die Indices von den beiden Kindern beschreiben wir auch mit $j_1,j_2$

Wir haben jetzt drei Fälle die wir betrachten müssen:

Fall 1: $b_1\le b_2\le a$ : Die Struktur ist richtig und somit müssen wir hier nichts verändern -> a ist am größten von seinen Kindern. Fall 2 und 3: $b_1<a<b_2$ Sowie $a<b_1<b_2$: In diesen Fällen ist es so, dass a kleiner als ein oder beide Element ist und somit der Heap getauscht werden muss. Wir müssen in beiden Fällen $b_2$ austauschen, da es das größte Element ist, welches nach Definition eines Max-Heap in die Wurzel muss. Haben wir jetzt $a$ mit $b_2$ getauscht, ist auf der Stufe $i$ die Struktur richtig. Aber jetzt kann bei dem Kind, wo der Tausch vorgenommen wurde ein Sortier-Fehler auftreten. ( etwa, dass $a$ auch da kleiner ist, als die Kinder von diesem Zweig). Gelöst wird das, indem Heapify rekursiv aufgerufen wird und hier erkennen wird, dass die Ordnung nicht stimmt. Sobald das geschieht, tritt wieder einer der drei Fälle auf.

Heapify Runtime:

Betrachten wir den vorherigen Ablauf, dann sehen, wir dass der Worst-Case dann eintritt, wenn wir jede Schicht vertauschen müssen. Daraus folgt dann besagte Laufzeit von :: $\mathcal{O}(\log (n))$ ^1704708670574

[!Warning] Das klingt eigentlich sehr gut! $\log (n)$ ist jetzt nicht konstant, aber dennoch viel besser als eine polynomielle Laufzeit!

ExtractMin/Max:

Folgend betrachten wir Extract-Min/Max als Operation auf / mit einem Heap: Ihr Name suggeriert bereits, was sie erfüllen möchte. Wie läuft diese Operation ab und wie reparieren wir den Heap? #card

[!Definition] Extract max / min element and repair heap: Wir wissen, dass das kleinste/größte Element immer in der Wurzel (root) liegt. Demnach können wir das kleinste Element einfach entnehmen, was in $\mathcal{O}$ passiert. Anschließend haben wir damit aber die Heap-Eigenschaft verletzt und müssen sie wieder herstellen.

Wir müssen jetzt irgendwie ein Element einspeisen, welches dann den Baum durchläuft und einsortiert wird, denn dabei wird er wieder sortiert.

Erfüllt wird dies jetzt dadurch, dass wir das letzte Element im Baum nehmen und ganz vorn einsetzen. Wir löschen dabei seinen originalen Eintrag. Jetzt durchläuft das neue Element den Heapify Prozess und somit wird das kleinste Element extrahiert und ausgegeben. ^1704708670579

[!Question] Wie schnell ist das extrahieren des kleinsten/größten Element? #card Die Laufzeit beschreiben wir jetzt mit der Summe aus dem Entfernen des Elements ($\mathcal{O}(1)$) und dem sortieren des Heaps ($\mathcal{O}(H\ddot{o}he(T))$). Wir wissen, dass Konstanten entfernt werden können und resultieren mit folgender Laufzeit: $mathhcalO(H\ddot{o}he(T))$, denn der Sortierprozess Heapify brauch genau diese Zeit. ^1704708670584

[!Example] Beispiel: Betrachten wir folgenden Baum, aus welchem wir das erste Element entnommen haben. Anschließend haben wir den Knoten ( bzw. das Blatt, weil es keine Kinder hat) mit dem Wert $5$ genommen und in die Wurzel gepackt. Es wird jetzt durch den Sortier-Ablauf gesetzt und dabei das kleinste Element in die Wurzel geschoben. ![[Pasted image 20231029184638.png]]

IncreaseKey (bei Min-Heap):

Mit IncreaseKey möchten wir eine Funktion einführen, die in einem Heap $H$ den Wert eines Knoten $v$ erhöhen wird. Passiert dies, verletzen wir wahrscheinlich die Heap-Eigenschaft und müssen sie wieder herstellen. Wie können wir sie wiederherstellen? #card Haben wir den Wert angepasst, müssen wir sie (bei einem Min-Heap) insofern herstellen, dass der Wert des Knoten ( gerade aktualisiert ) kleiner als seine Kinder sein wird. Wir müssen jetzt also mit dem Kind tauschen, das den kleineren Wert hat ( also in der Dreier-Konstellation der kleinste Wert verfügbar). Es kann jetzt auftreten, dass der neue Wert an der neuen Stelle immer noch größer ist, als die Kinder dessen. Demnach müssen wir unter Umständen weiter den Heap-ausbauen. ^1704708670590

Aus dieser Betrachtung lässt sich jetzt folgende Laufzeit (Worst-case) resultieren #card

[!Info] Laufzeit IncreaseKey: Im Worst-Case würden wir den Wert in der Wurzel erhöhen und dann bei jedem Durchlauf in jeder Schicht eine Sortierung stattfinden lassen. Ferner erhalten wir folgende Laufzeit: $$\mathcal{O}(h)=\mathcal{O}(\log n)$$ ^1704708670595

[!example] Beispiel für Max-Heap: Bei einem Max-Heap möchte man immer den größten Wert im Root haben. Daher ist bei dieser Struktur Decrease-Key gleich, wie Increase-Key bei einem Min-Heap. Wir sehen hier, dass der Wert anschließend nach unten propagiert und sortiert werden muss: ![[Pasted image 20221028105148.png]]

DecreaseKey (bei Min-Heap):

Mit Decrease-Key beschreiben wir die Operation, dass wir bei einem Heap $H$ bei Knoten $v$ den Wert verringern. Dabei kann jetzt auch wieder die Heap-Eigenschaft verletzt werden. Wie können wir diese Eigenschaft beibehalten bzw reparieren? #card Wenn wir an Knoten $v$ einen Wert verringern, kann es sein, dass der Parent-Wert jetzt größer ist, als $v$. Das heißt, wir müssen entsprechend nach oben propagieren und somit $parent(v)=v,v=parent(v)$ setzen bzw. tauschen. Aus diesem Tausch kann es sein, dass $parent(v)$ wieder falsch ist und somit auch korrigiert werden muss. Dafür werden wir auch wieder den Prozess wiederholen und diesen Wert mit dessen Parent austauschen. ^1704708670601

Auch hier können wir eine (Worst-case) Laufzeit evaluieren: #card

[!Tip] Laufzeit DecreaseKey: Im Worst-Case würden wir hier ganz unten im Baum einen Wert so verkleinern, dass er im gesamten Baum dem kleinsten entspricht. Das heißt er müsste jede Schicht traversieren und somit jedes mal eine Sortierung vornehmen. Aus dieser Betrachtung erhalten wir folgende Laufzeit: $$\mathcal{O}(h)=\mathcal{O}(\log n)$$ Denn auch hier entspricht die Laufzeit dann der Höhe des Baumes ^1704708670606

[!Example] Beispiel für Max-Heap: Betrachten wir folgenden Baum und tauschen jetzt den Wert $4$ zu $15$. Da er sich weit unten befindet muss der darüber liegende Wert angepasst werden. Dies müssen wir in nächsten Stufe auch nochmal machen. ![[Pasted image 20221028105418.png]]

Heap bauen:

Setzen wir voraus, dass wir einen unsortierten Array der Größe $n$ erhalten haben. Folglich ist unsere Aufgabe jetzt: baue einen Heap daraus! Also das etablieren eines Heaps, der entsprechend geordnet ist wie machen wir das? #card

First (naive) solution:

create empty heap and insert all elements one after the other. This way we can guarantee the heap property for each new element:

Array C; 
A = empty heap
for i = 1 to n 
	InsertElement(AC(i))

^1704708670612

Running time: #card We can denote the running time with $\mathcal{O}(n\cdot (\log n))$ because:

• for each new element we are running the heap-algorithm, so $n$-items and for each we run the heapify Algorithm that takes $\log n$ at worst. Conclusion:
• considering that the Heap is only increasing over time we could likely decrease the amount of operations and take less time.
• Actually we can show / proof that it will take less time ( we are omitting it here because we will do it in the second solution too)

Second solution:

How can we construct a Heap out of a given amount of elements? #card Write all elements in a (binary) tree in a random order. Starting from the leafs ( so the lowest points in the tree) call heapify for each vertex ( so we are sorting it from the ground up). The Pseudo-Code may look as follows:

Array C;
A = complete binary tree with elements of C in random order 
for i = n to 1 (inverse)
MaxHeapify(A,i); # traversing from bottom to top 

^1704708670618

Wir können hier auch sagen, dass die Laufzeit im Worst-Case $\mathcal{O}(n\cdot (\log n))$ sein wird.

Correctness of 1 and 2 Solution:

Beide Algorithmen funktionieren prinzipiell, weil wir mit Heapify immer die Korrektheit der Eigenschaft garantieren können und wollen. Wir können diese Eigenschaft der zweiten Lösung auch entsprechend beweisen.

[!Quote] What to proof After the for-loop of BuildHeap has been called on all vertices in level h, all trees rooted in level h and below are correct heaps

Dies können wir durch Induktion in Abhängigkeit von $h$ beweisen: Nehmen wir dabei an, dass wir einen Heap mit Höhe $H$ haben.

Als Induktionsanfang setzen wir: In layer $H$ ( der tiefsten Schicht, als ganz unten) sind nur Blätter und somit ist ihre Heap-Eigenschaft schon erfüllt.

Induktions-Hypothese: Nehmen wir an, dass die Heap-Eigenschaft für Schicht $h$ stimmt, dann stimmt sie auch für $h+1,H$, also dem gesamten Baum.

Induktionsschritt: von $h$ zu $h-1$: Für jeden Knoten $i$ im Level $h-1$ rufen wir heapify auf. Gemäß der Induktions-Hypothese sind alle Unter-Bäume von $i$ ( dem betrachteten Baum) bereits richtige Heaps. Wenn wir jetzt $heapify(A,i)$ rufen, dann wird sie auch für Knoten $i$ erfüllt.

Caveat dieses Aufbaus: Buildheap would not work if we go trough the vertices(Knoten) in increasing order: $1,ldots,n$ (start in the root and not at the bottom of the tree). Denn dann prüfen wir nicht rückwirkend, ob die Eigenschaft eingehalten wurde / wird.

[!Quote] solution for given caveat Whenever we call heapify at a given node, we cannot assure that the leafs and their children are sorted correctly, thus it could occur that we sort some key values incorrectly. This implies that its important to start at the bottom of this tree and heapifying-up until we reach the root .

Running time:

Upper bound is given with O(n log n) >> n inserts and heapify takes log(n) to sort accordingly.

[!Important] why this not 100% correct: Yet we miss the aspect, that the binary tree will grow over time and is smaller than n at the start, thus reducing the time to access and sort the heap.

Aus diesem Grund können wir dei Running-Time noch etwas sinniger / besser bzw. genauer berechnen:

Wir wissen folgend, dass die Laufzeit von Heapify von der Höhe des Baumes, der betrachtet wird, abhängig ist. Also $\mathcal{O}h(v)$, wobei $v$ der derzeitig ausgewählte Knoten ist, der danach rekursiv betrachtet wird. Wir wissen weiterhin, dass die Höhe meist viel kleiner als $\log n$ ist. Wir also bei diesen Heapify-Operationen gar nicht auf $\log n$ stoßen können / werden. Mit dieser Eigenschaft können wir jetzt etwas einschränken:

• Mit $H$ meinen wir die Höhe des gesamten Baumes
• wenn wir einen Knoten in Schicht / Höhe $h(v)$, müssen wir maximal $H-h(v)$ Swap-Operationen durchführen ( also bis ganz zum Grund des Baumes von Punkt v).
• Weiterhin wissen wir, dass wir in diesem Baum $2^h$ Knoten haben werden. Aus diesen Betrachtungen können wir jetzt folgende Laufzeit entziehen: $$\sum _{h=0}^H{w}^h\cdot (H-h)$$ wir können diese Summe jetzt noch entsprechend verkleinern: $$T(n)=2\cdot T(n)-T(n)=\sum _{h=0}^H{2}^{h+1}\cdot (H-h)-\sum _{h=0}^H{2}^h\cdot (H-h)$$ $$=2^1(H-0)+2^2(H-1)+\dots +2^H\cdot 1+2^{H+1}\cdot 0-2^0(H-0)-2^1(H-1)-2^2(H-2)-\dots -2^H\cdot 0$$ $$2^1+2^2+\dots +2^H-H=2^{H+1}-2$$ Setzen wir jetzt für $H=\log n$ ein, dann werden wir Laufzeit $\mathcal{O}(n)$ erhalten!

Priority Queues | example usage of Heaps:

Wir können eine Priority-Queue verschieden implementieren, aber werden sehen, dass es relativ einfach ist, wenn man dies mit einem Heap umsetzt.

queue could be build with array or list, yet some issues could occur :: ^1704708670623 extracting and finding a priority within a sorted array is fast, yet adding a new value is not and all preceeding values of that given array have to shift to the right. with a unsorted array the extraction and search is rather slow, poses another problem.