bullhost.de - PC Lexikon

Definition bzw. Erklärung: Heapsort

Bei dem Begriff Heapsort handelt es sich um einen im Jahr 1964 von J. Williams entwickelten schnellen Algorithmus zur Sortierung von Daten. Beim Heapsort wird der Datenbestand in einem binären Baum, also in eine Verästelungsstruktur, in der jeder Knoten maximal 2 Äste hat, umgewandelt. Dann werden, beginnend von unten nach oben und von links nach rechts die Elemente der einzelnen Äste paarweise so vertauscht, dass sich das jeweils größte Element im Knotenpunkt befindet, bis das größte Element des kompletten Datenbestands ganz oben in der Baumstruktur steht. Dieses wird daraufhin entfernt und das am weitesten rechts stehende Element der untersten Ebene rutscht nach oben nach. Dieser Vorgang wird solange wiederholt, bis der Baum abgebaut it, und damit alle Elemente sortiert sind. Diese Art der Sortierung gehört mit zu den schnellsten, ist jedoch im Durchschnitt einwenig langsamer als der Quicksort-Algorithmus.

Alle Texte, Grafiken sowie das Design sind urheberrechtlich geschützt und dürfen nicht ohne Zustimmung von Bullhost Internet Service weiter verwendet werden.