HeapSort, třídění haldou
Algoritmus pro Stromové Třídění.
Nástin algoritmu a datové strukury:
- Halda (pozor, není halda jako Halda): binární strom, všechny hladiny jsou zcela zaplněné kromě poslední a ta se zaplňuje zleva
- pak ho můžu uložit do pole (indexovaného od 1:() – prvky jsou oindexované odshora dolů po hladinách zleva doprava
- platí: hodnota prvku < (nebo =) hodnoty všech jeho synů (takže minimum je nahoře)
- každý další prvek setříděné posloupnosti dostanu takto:
- vezmu minimum (nahoře) a nahradím ho posledním prvkem (vpravo dole), abych zachoval tvar haldy
- teď jen zatřídím tu poslední hodnotu tak, že ji porovnávám s menším ze synů a prohazuji, dokud ji nedostnanu, kam patří
- na začátku si ale musím vytvořit haldu, složitost vypadá jako O(N log N), ale vlastně je jen O(N), když se to spočítá pořádně
- celková složitost O(N log N) (i odebírání)
