Algorithmen I, SS 2015, gehalten am 27.05.2015, Vorlesung 13 (+ Übung)
1 hour 11 minutes Posted Dec 3, 2015 at 3:25 pm.
Prioritätslisten
Prioritätslisten (priority Queues)
Prioritätslisten – Anwendungen
Binäre Heaps
Implizite Baum-Repräsentation
deletMin: Beispiel
Binärer Heap – Analyse
Beispiel: Binärer Heap – Konstruktion
Binärer Heap – Konstruktion
Ein nützlicher Rechentrick
Heapsort: Beispiel
Heapsort
Heapsort – Quicksort – Mergesort
Adressierbare Prioritätslisten
Adressierbare Prioritätslisten: Anwendungen
Adressierbare Binäre Heaps
Prioritätslisten: Zusammenfassung
Was haben wir jenseits von Prioritätslisten gelernt?
Sortierte Folgen
Statisch: Sortiertes Feld mit binärer Suche
Binäre Suche – Beispiel: k = 15
Dynamische Sortierte Folgen – Grundoperationen
Mehr Operationen
Noch mehr Operationen
Abgrenzung
Sortierte Folgen – Anwendungen
Anwendungsbeispiel: Best Fit Bin Packing
Binäre Suchbäume
Varianten, Bemerkungen
locate(k)
locate(k) – anderes Beispiel
Invariante von locate(k)
Ergebnisberechnung von locate(k)
Laufzeit von locate(k)
Naives Einfügen
Beispiel
Roadmap
Perfekter Binärbaum
(Max)Heap und Suchbaum
Perfekter Binärbaum
(Max)Heap und Suchbaum
Heapsort mit Max-Heap
(Max)Heap und Suchbaum
Heapsort
Heapsort mit Max-Heap
Adressierbare binäre Heaps
Anwendungsbeispiel
Adressierbare binäre Heaps
0:00
1:11:14
Show notes
13: Vorlesung und Übung |VorlesungÜbung
Watch Video
