Mathematik Informatik Philosophie Diverses Kontatkt FAQ
Benutzername:
Passwort:
 Home > News
Freitag, 26. Mai 2017 13:15 
HeapSort - wie man mit einem "Haufen" sortieren kann!
 
Geschrieben von Alexander am Donnerstag, 29. Juni 2006

Der Heap-Sort ist ein grundlegender Algorithmus der in (fast) keiner Vorlesung "Datenstrukturen und Algorithmen" ausgelassen wird.

Dieses Sortierverfahren wird meist im Kontext binärer Bäume eingeführt; dies ist dadurch begründet, dass der natürliche Definitionsbereich der besonderen Datenstruktur "Heap" ein binärer Baum ist. Dennoch wendet man in der Praxis den Sortieralgorithmus Heapsort für gewöhnlich auf normalen Arrays an.

Die Methode des Sortierens durch direkte Auswahl beruht auf dem wiederholten Auslesen des kleinsten Schlüssels aus (den restlichen) n Elementen. Auf einem ähnlichen Prinzip basiert der Haepsort, doch die zu Grunde gelegte Datenstruktur Heap (zu deutsch Haufen) behält mehr Informationen und ist deshalb deutlich schneller als die 'normale' Variante des Sortierens durch direkte Auswahl.

Der Inhalt dieses Dokuments behandelt überwiegend die heuristische Vorgehensweise des Algorithmus. Es werden viele Beispiele durchexerziert und erklärt. Am Rande wird auf die Kosten und evtl. Beweis der Korrektheit eingegangen. Die notwendigen Algorithmen für eine mögliche Implementation werden ausführlich dargestellt und hinterleuchtet.

Im Einzelnen werden behandelt:

  • Vergleich mit naiven Sortierverfahren: Einfügen, Löschen, Suchen
  • Definition, Heap-Bedingung, Minimums-Heap und Maximums-Heap, Alternative Formulierung der Heap-Bedingung für binäre Bäume, Beispiele
  • Algorithmen: StelleHeapBedingungHer(), ShiftDown() ["versickern"], EntferneExtrema(), ErzeugeHeap() - konkrete Beispiele zu allen Algorithmen.
  • Analyse des Heap-Sorts

Heap-Sort
Alle Logos und Warenzeichen auf dieser Seite sind Eigentum der jeweiligen Besitzer und Lizenzhalter.
Im übrigen gilt Haftungsausschluss. Weitere Details finden Sie im Impressum.
Die Inhalte dieser Seite sind als RSS/RDF-Quelle verfügbar.
Die Artikel sind geistiges Eigentum des/der jeweiligen Autoren,
alles andere © 2004 - 2017 by mathematik-netz.de

Seitenerstellung in 0.0727 Sekunden, mit 54 Datenbank-Abfragen