Něco ke stažení
Články a návody
Poezie
Odkazy
Heap sort
Způsob třídění, nazývaný Heapsort, využívá dobré vlastnosti binárních stromů a dosahuje tak časové složitosti O(n*log n) pro data o velikosti n.
Postup třídění pomocí Heapsortu je následující - vytvoříme prázdnou binární haldu, do které postupně přidáváme tříděné prvky. Ty přidáváme do poslední hladiny co nejvíce vlevo. Pokud má otec nově přidaného vrcholu větší hodnotu než nový vrchol, tak je prohodíme a děláme to tak dlouho, dokud se nový vrchol nedostane do kořene nebo se nezarazí o otce s nižší hodnotou.
Po přidání posledního ji zase rozebereme, budeme postupně brát prvek v kořeni. Pro tento prvek z definice haldy platí, že je ze všech prvků v haldě nejmenší a tak budeme postupně skládat výslednou setříděnou posloupnost od nejmenších prvků. Po odebrání minima z haldy musíme ještě haldu upravit, abychom dostali korektní haldu. Úprava bude podobná obrácenému přidávání prvků. Vezmeme prvek v poslední hladině co nejvíce vpravo a uděláme z něj kořen. Porovnáme ho s oběma syny a pokud je alespoň jeden menší, prohodím menšího ze synů s otcem. Tak zase postupuji stromem dolů, dokud nejsou oba synové větší, nebo dokud se prvek nedostane do listu.
Při implementaci Heapsortu je pro reprezentaci haldy místo klasického uložení prvků ve stromu s uzly spojenými pomocí ukazatelů vhodnější použít reprezentaci haldy polem. To uděláme následovně. V položce pole s indexem 1 (budu pole indexovat od 1) bude uložen vrchol haldy, v políčkách 2 a 3 jeho synové, 4 a 5 budou synové 2, 6 a 7 synové 3, atd. Tedy i-tá položka pole bude reprezentovat uzel s otcem na pozici i div 2 (kromě kořene) a syny na pozicích 2*i a 2*i+1.
Tvorba haldy bude vypadat tak, že nejprve vložím prvek na pozici 1, pak na pozici 2 a porovnám hodnotu s políčkem 1 (a případně prohodím), vložím prvek na pozici 3 a porovnám s 1, vložím prvek na pozici 4 a porovnám s 2,....
Touto reprezentací tak snadno splním požadavek přidávání prvků "do poslední hladiny haldy co nejvíce vlevo", jak je požadováno výše, neboť to zde znamená ještě nepoužité políčko s nejmenším indexem. U reprezentace pomocí ukazatelů bychom museli dělat složitější konstrukce.
Ačkoliv se úpravy haldy mohou zdát časově náročné, výsledek se chová dobře. Přidání prvku má časovou náročnost O(log n), neboť halda má log n úrovní a při vkládání je v nejhorším případě projdem všechny. Určení minima haldy je snadné - je to vždy kořen, takže složitost je O(1). No a nakonec odebíráme minimum, což má složitost O(log n) (tj. složitost tedy opět odpovídá výšce stromu). Celkem tedy vložíme n prvků, to je složitost O(n*log n). Pak strom zase rozebereme, což pro n hodnot znamená časovou složitost O(n*log n), tedy výsledná složitost je O(n*log n).
Následující příklad není můj, ale už si nepamatuju, kde jsem ho našel. (a nechce se mi to psát znovu v C)
Program HeapSort;
const VELIKOST = 10;
type Pole = array [1..VELIKOST] of integer;
var VelikostHaldy:Integer;
Procedure NaplnHaldu(var Halda:Pole; P:Pole);
var i,aktualni,predek,pom:integer;
begin
for i:=1 to VELIKOST do
begin
Halda[i]:=P[i];
predek:=i div 2;
aktualni:=i;
while (aktualni<>1) do
begin
if (Halda[predek]>Halda[aktualni]) then
begin
pom:=Halda[aktualni];
Halda[aktualni]:=Halda[predek];
Halda[predek]:=pom;
aktualni:=predek;
predek:=predek div 2;
end
else aktualni:=1;
end;
end;
VelikostHaldy:=VELIKOST;
end;
Function VyjmiMinimum(var H:Pole):integer;
var Vrchol,Min,Pom:integer;
begin
Min:=H[1];
H[1]:=H[VelikostHaldy];
Dec(VelikostHaldy);
vrchol:=1;
while (vrchol*2<=VelikostHaldy) and
((H[vrchol]>H[vrchol*2]) or (H[vrchol]>H[vrchol*2+1])) do
begin
if H[vrchol*2] < H[vrchol*2+1] then
begin
pom:=H[vrchol];
H[vrchol]:=H[vrchol*2];
H[vrchol*2]:=pom;
vrchol:=vrchol*2;
end
else
begin
pom:=H[vrchol];
H[vrchol]:=H[vrchol*2+1];
H[vrchol*2+1]:=pom;
vrchol:=vrchol*2+1;
end;
end;
VyjmiMinimum:=Min;
end;
Procedure Trideni(var P:Pole);
var i:integer;
H:Pole;
begin
NaplnHaldu(H,P);
for i:=1 to VELIKOST do P[i]:=VyjmiMinimum(H);
end;