HeapSort und Sortieren in linearer Zeit Flashcards
1
Q
Wie ist ein Heap Aufgebaut, mit welcher Datenstruktur ist er implementiert?
A
- Ein Heap ist ein fast vollständiger binärer Baum und kann als Array implementiert werden.
- Die Regel lautet: Bei einem Max-Heap ist die Wurzel des Teilbaums das größte Element
- Min-Heap Analog dazu
2
Q
Wie lauten die Indizes für die Wuzel, Eltern und Kinder eines Elements in einem Heap?
A
- Wurzel A[1]
- Eltern A[i] = A[⌊i/2⌋]
- linkes Kind A[i] = A[2i]
- rechtes Kind A[i] = A[2i + 1]
3
Q
Welche Operationen hat ein Heap und was ist ihre Laufzeit Komplexität?
A
- insert O(lg n)
- get min/max O(1)
- extract min/max O(lg n)
- update O(lg n), wenn man den Index weiß, O(n) wenn man ihn nicht weiß
- heapify O(n)
4
Q
Wie funktioniert Max-Heapify?
A
- Man geht das Array von hinten nach vorne durch
- Trifft man auf ein Element, welches die Max-Heap Eigenschaft verletzt tauscht man es mit dem größten Kind
- Wiederholt das mit diesem Element solange, bis es an der richtigen Stelle ist
- Gehe zum nächsten Element über
- Min-heapify funktioniert analog (man tauscht mit dem kleineren Kind)
5
Q
Wie funktioniert Insert bei einem Heap?
A
- Wir fügen das Element ans Ende des Arrays ein
- “Schieben” es solange nach oben bis es passt
- Laufzeit ist dabei abhängig von der höhe des Baumes
- Da ein Heap ein balancierter Baum ist O(log n)
6
Q
Wie funktioniert extract min/max?
A
- Wir dürfen die Wurzel nicht einfach löschen
- Wir tauschen die Wurzel mit dem letzen Element im Array
- Positionieren die neue Wurzel an die geeignete Stelle, durch tauschen mit dem größeren/kleineren Kind
7
Q
Wie funktioniert Update bei einem Heap?
A
- Wollen wir den Wert eines Knotens verändern müssen wir wissen ob wir diesen erhöhen oder verkleinern
- Jenachdem müssen wir diesen Knoten dann nach oben oder unten Positionieren
- Min: verkleinern -> weiter nach oben, vergrößern -> weiter nach unten
- Max: verkleinern -> weiter nach unten, vergrößern -> weiter nach oben
- Kennen wir den Index des Elements nicht, müssen wir diesen erst suchen, was n Zeit beansprucht
8
Q
Warum ist die bestmöglichste Obere Schranke O(n lg (n)) bei Sortierverfahren, die Vergleichen?
A
- Man erstellt einen Entscheidungsbaum für den gewünschten Algorithmus
- Allgemein ist die Untere Schranke für den Entscheidungsbaum Ω(n lg n)
- Dadurch sind Heap, Merge und Quicksort optimale Comparison Sort Algorithmen
9
Q
Wie funktioniert HeapSort?
A
- Zuerst müssen wir das Array heapifien
- Danach rufen wir extract auf und heapifien erneut
- Laufzeit: O(n * lg n)
- Durch Code Tuning schlägt QuickSort HeapSort
- HeapSort in dieser “Standard” Form ist instabil
- HeapSort ist inline
10
Q
Was ist eine Prioritätsliste?
A
- Eine Liste, die nach Priorität sortiert ist
- Eine normale liste bietet sich hierfür an aber ein Heap ist besser geeignet
- Das Einfügen geht schneller Heap: O(lg n) Liste: O(n)
- Das Updaten, wenn man den Index hat kann langsamer sein Heap(lg n) Liste: O(i)
- Kennt man den Index nicht ist es gleich schnell beides O(n)
- Search ist gleichschnell beides O(n)
11
Q
Wie funktioniert Counting-Sort?
A
- Zuerst braucht man ein Array C, welches so groß ist, wie die größte Zahl im zusortierenden Array A
- Wir setzen in Array C alle Werte auf 0
- Wir gehen Array A durch
- Bei einer 3 bspw. erhöhen wir den Wert beim Index 3 um eins in Array C
- Wir gehen durch unser Array C durch (Starten bei 2) und rechnen immer C[i] = C[i] + C[i-1] also immer den aktuellen Wert plus den des Vorgängers
- Wir erstellen ein neues Array B
- Wir iterieren von hinten durch Array A
- Bei bspw. 3 gehen wir in Array C zum Index 3 und der Wert ist der Index, wo die Zahl 3 in Array B eingefügt wird
- Wir ziehen 1 bei dem Index 3 ab (im Array C)
12
Q
Was sind Eigenschaften sowie vor und nachteile von CountingSort? Warum ist es schneller als O(n lg n)?
A
- Laufzeit in O(n + k) und es ist stabil (bei einem Schlüssel)
- Vorteile: Lineare Laufzeit, einfach zu implementieren
- Nachteil: nicht inline, kann sehr viel speicherplatz benutzen, instabil bei mehreren Schlüssekn
- Es ist schneller, da es keine Vergleiche nutzt
13
Q
Wie funktioniert Radix-Sort?
A
- Wir schreiben die Zahlen untereinander auf
- Sortieren hinten angefangen die einzelnen Spalten durch nach dem Prinzip von CountingSort
