HeapSort

Třídění pomocí "haldy"

V HeapSortu se nejdříve vytvoří haldy(piramidy) ve kterých platí, že prvek otec ma pod sebou dva syny, kteří jsou menší než on sám. A synové jsou pak otci pro další dva prvky. Halda je datová struktura, jejíž každý prvek je uzel se dvěma následníky. Pro Heapsort jsou vyžadovány ještě další dvě podmínky: A, Každé patro haldy musí být kompletně zaplněno, pouze poslední patro může mít prvky napravo prázdné (viz obrázek). B, Každý uzel musí mít pouze větší syny než je on sám. Při přidání dalšího prvku se musí pole znovu uhaldovat-prvek se pridá jako otec a pokud je menší než synová tak se vymění s největším synem, pokud je i pak nejaký syn vetší než přídané číslo, tak se mění dál.

Takto vypadá Heapsort v Delphi

var PPole : ^TPoleCisel;

procedure CreateHeap(l,r : integer);

var
i,j,Prvek : integer;
Sestup : boolean;

Begin
i := l;
j := i*2;
Sestup := true;
prvek := PPole^[i];

while Sestup and (j < r) do
begin
if (j < r) and (PPole^[j] < PPole^[j+1]) then j := j+1;
Sestup := Prvek < PPole^[j];

if Sestup then
begin

PPole^[i] := PPole^[j];
i := j;
j := 2*i
end;
end;

PPole^[i] := Prvek;

end;

procedure HeapSort(var Pole : TPoleCisel);

var
l,r,pom : integer;

begin
PPole := @Pole;

for l := (length(Pole) div 2) downto 0 do CreateHeap(l,length(Pole));

for r := length(Pole) downto 1 do
begin
pom := Pole[0];
Pole[0] := Pole[r];
Pole[r] := pom;
CreateHeap(0,r-1);
end;

end;