Erkläre Heap Sort und Heapify.
Erkläre Bubble Sort Bubble Sort ist ein Sortieralgorithmus zum Sortieren von Arrays von Zahlen oder anderen vergleichbaren Dingen. Er funktioniert, indem zwei benachbarte Elemente vertauscht werden, so dass das größere Element danach rechts steht. Dieser Prozess wird für jede Position von links nach rechts wiederholt. Danach befindet sich die größte Zahl im Array an der letzten Position. Als nächstes beginnt der Algorithmus wieder ganz links und tauscht benachbarte Elemente nach rechts, aber diesmal kann er vor der letzten Position stoppen, da die größte Zahl bereits dort ist. Es wird Bubble Sort genannt, da die größte Zahl immer "aufsteigt".
Hier ist ein Beispiel:
```
4 8 3 6 1
# tausche 4, 8 nicht, da 8 > 4
4 8 3 6 1
# tausche 8, 3
4 3 8 6 1
# tausche 8, 6
4 3 6 8 1
# tausche 8, 1; 8 ist jetzt richtig
4 3 6 1 8
# tausche 4, 3
3 4 6 1 8
# tausche 4, 6 nicht, da 6 > 4
3 4 6 1 8
# tausche 1, 6; 6 ist jetzt richtig
3 4 1 6 8
# tausche 3, 4 nicht, da 4 > 3
3 4 1 6 8
# tausche 4, 1; 4 ist jetzt richtig
3 1 4 6 8
# tausche 3, 1; 3 ist jetzt richtig
1 3 4 6 8
# Array ist sortiert
```
**Heap Sort**
Heap Sort ist ein effizienterer Sortieralgorithmus als Bubble Sort, der ebenfalls Zahlen oder ähnlich vergleichbare Dinge sortiert. Er verwendet einen Heap (kann maximal oder minimal sein), der ein binärer Baum ist, bei dem ein Knoten immer größer oder kleiner als beide seiner Kinder ist. Es dauert `n*log_2(n)` Zeit, um den Heap zu erstellen, da jedes Element eingefügt werden muss und höchstens `log_2(n)` Ebenen des Baums durchlaufen werden können.
Dann ist der Wurzelknoten bereits das Maximum, sodass er sofort aus dem Heap genommen und in eine sortierte Liste eingefügt werden kann. Dann wird ein Blattknoten an die Stelle des Wurzelknotens gesetzt und der Baum wird neu sortiert, was höchstens `log_2(n)` Zeit dauert. Dann wird der Wurzelknoten erneut aus dem Heap genommen und in die sortierte Liste eingefügt. Dieser Vorgang wird wiederholt, bis der Heap leer ist, was insgesamt `n*log_2(n)` Zeit dauert.
Hier ist ein Beispiel zum Sortieren von 3 Zahlen:
```
##########################
# Erstelle den Heap. #
##########################
7 2 9
# Füge 7 zur Wurzel hinzu:
# (7)
2 9
# füge zwei zum nächsten Blattknoten hinzu:
# 7
# └── 2
# Ist es ein Max-Heap? Sind alle Kindknoten kleiner als ihre Elternknoten? Ja.
9
# füge neun zum nächsten Blattknoten hinzu:
# 7
# ├── 2
# └── 9
# Sind alle Kindknoten kleiner als ihre Elternknoten? Nein.
# Bewege neun nach oben:
# 9
# ├── 2
# └── 7
# Sind alle Kindknoten kleiner als ihre Elternknoten? Ja.

# Es sind keine Elemente mehr übrig. Der Heap ist erstellt.

###########################
# Jetzt sortiere aus dem Heap. #
###########################
# Nimm den Wurzelknoten und füge ihn in die Liste ein:
# -
# ├── 2
# └── 7
9
# Ersetze den Wurzelknoten durch den letzten Blattknoten:
# 7
# └── 2
# Sind alle Kindknoten kleiner als ihre Elternknoten? Ja.
# Nimm den Wurzelknoten und füge ihn in die Liste links ein:
# -
# └── 2
7 9
# Ersetze den Wurzelknoten durch den letzten Blattknoten:
# (2)
# Sind alle Kindknoten kleiner als ihre Elternknoten? Ja.
# Nimm den Wurzelknoten und füge ihn in die Liste links ein: 
# (_)
2 7 9
# Der Baum ist leer, das bedeutet, dass das Sortieren abgeschlossen ist!
```

---

**Heapify**

Anstatt wie zuvor nach oben zu justieren, betrachtet Heapify jeden Knoten, beginnend mit dem rechtesten Blattknoten, und geht nach links, bis es etwas erreicht, das kein Heap ist. Sobald es einen Knoten erreicht, bei dem die Kinder nicht alle kleiner als der Elternknoten sind, wird der Wert des Wurzelknotens mit dem größten Kind ausgetauscht. Dies wird mit dem ausgetauschten Kindknoten wiederholt, bis es den Boden des Baums erreicht hat. Dann wird dieser ganze Vorgang wiederholt, bis die Wurzel des gesamten Baums erreicht ist. Dieser Vorgang dauert immer noch höchstens `n*log_m(n)` Zeit, wenn alle Elemente jedes Mal zum Boden des Baums verschoben werden müssen, aber er ist nützlich, um Bäume im Allgemeinen in Heaps zu transformieren.
Hier ist ein Beispiel mit einem binären Baum mit vier Elementen:
```
# beginne mit einem nicht-max-Heap binären Baum:
2
├── 9
│   └── 11
└── 7
# 11 ist ein Heap, weil es keine Kinder hat, weiter zu 7
# 7 ist ein Heap, weil es keine Kinder hat, weiter zu 9
# 9 ist kein Heap, weil 11 größer ist. Tausche aus.
2
├── 11
│   └── 9
└── 7
# 9 ist jetzt ein Heap. Weiter zu 2.
# 2 ist kein Heap. Sowohl 11 als auch 7 sind größer. Tausche mit 11, da es das größte ist:
11
├── 2
│   └── 9
└── 7
# 2 ist immer noch kein Heap. Tausche mit 9:
11
├── 9
│   └── 2
└── 7
# 2 ist ein Heap und 11 ist die Wurzel. Wir sind fertig!
```