Heapsort Verfahren

[OrallY]

Das Heapsort-Verfahren ist eines unter vielen Sortierverfahren. Es benutzt, um es in ein Bild zu fassen, einen Baumdiagramm mit folgenden Voraussetzungen:
Jeder Knoten hat höchstens 2 Nachfolgerknoten, wobei keiner der beiden Nachfolger größer sein darf, als der Knoten selbst. Ist diese Vorausetzung für jeden Knoten des Baumes gegeben, befindet sich an der Wurzel des Baumes der größte Wert.

Eine kleine "Skizze" um zu verdeutlichen, wie der Array in den Baum transferiert ist (hoffentlich kann man es erkennen ):

Code:

Syntax und Legende: 
   o:Index

   o = knoten
  Index = Index des Werts im Array, der diesem Knoten zugeteilt wird
  /\ = Verbinungslinien die die Zugehörigkeit der Knoten andeutet


                                      o:0
                                    /   \ 
                                   o:1   o:2
                                 / \     / \
                                o:3 o:4 o:5 o:6
                               / \ / \ / \ / \
                                     usw.

Heapsort eignet sich vorallem für größere Datenmengen, erziehlt bei einer Vorsortierung sogar ein besseres Ergebnis als Quicksort, da es durch den Baumaufbau so oder so jede evtl. vorhandene Ordnung wieder zunichte macht . Qicksort weist schon bei einer geringen Vorsortierung eine schlechtere Laufzeit auf, als bei einem völlig unsortierten Array/Datenpacket.

Der Code:

Delphi-Quellcode:

{die AdjustHeap Prozedur ist dafür verantwortlich, die Baumstruktur aufzubauen}

procedure AdjustHeap(n: integer; var Data: array of integer; knot: integer);
var
  temp_knot_value, subknot: integer;
begin
  temp_knot_value := Data[knot];

  while knot < n div 2 do
  begin
    subknot := 2*knot+1; //Formel um Unterknoten herauszufinden, wobei 2*knot+2 der 2. Unterknoten ist.

    {Überprüfung, welcher der beiden Unterknoten größer ist; subknot wird der Index des größeren zugewiesen.}
    if (subknot < n - 1) and (Data[subknot] < Data[subknot + 1]) then
      Inc(subknot);


    {Wenn der größere der beiden Unterknoten nicht größer als der betrachtete Knoten ist, breche die Schleife ab ...}
    if temp_knot_value >= Data[subknot] then
      break;


    {... andernfalls tausche die Werte.}
    Data[knot] := Data[subknot];

    {Ein neuer Knotenindex wird gesetz, um eine Ebene im Baum tiefer zu wandern und den Unterknoten unter den gleichen Aspekten zu betrachten.}
    knot := subknot;

  end;
  Data[knot] := temp_knot_value;
end;

{eigentlich Prozedur}
procedure HeapSort(var Data: array of integer);
var
  knot, temp, i: integer;
begin
  i := Length(Data);

{Erstsortierung des Heaps/Baumes}
  knot := i div 2; //begonnen wird mit einem Knoten in der Mitte des Arrays
  while knot > 0 do
  begin
    Dec(knot);
    AdjustHeap(i, Data, knot);
  end;

  while i >= 0 do
  begin
    
    {da nun das erste Feld den größten Wert enthält, wird dieser mit dem letzten Feld vertauscht ...}
    temp := Data[0];
    Data[0] := Data[i];
    Data[i] := temp;

    AdjustHeap(i, Data, 0);
    Dec(i); {... und da der größte Wert nun am Ende steht, also schon einsortiert ist, wird der zu betrachtenden Bereich auf den noch unsortierten Teil festgesetzt}
  end;
end;

Bei jedem durchlauf von AdjustHeap ist der Wert mit dem Index 0 der größte Wert. Also wird er mit dem letzten Feld vertauscht. Da nun der Größte Wert am Schluss des Array steht, also schon einsortiert ist, braucht man dieses Feld nicht mehr in die Suche mit einzubeziehen. So erlangt der Array von hinten nache Vorne seine Ordnung.


Ich hoffe ich habe mit meinen Kommentaren helfen können, das nicht ganz so leicht zu durchblickende Verfahren verständlich zu machen. Am besten versteht man es, wenn man den Algorithmus Step by Step selbst mit Papier und Bleistift an einem kleinen Baum nachvollzieht. Ihr werdet staunen .