HeapSort, třídění haldou

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í)