Heapsort

Heapsort neboli třídění pomocí kupy (haldy, hromady) využívá hierarchické třídění. Každý nadřízený prvek má dva podřízené. Řazení má dva kroky.

1. Vystavíme strukturu tak, aby prvky byly seřazeny ve všech větvích. Ke 2 prvkům přiřadím 3 tak, aby byl větší byl nahoře.
2. Největší prvek dáme na konec pole. Ve zbylé části prvky postupně povyšujeme a nejvyšší dáme na konec neseřazené části pole.

$a_1$

$a_2$

$a_3$

$a_4$

$a_5$

$a_6$

$a_7$

$a_8$

$a_9$

$a_{10}$

$a_{11}$

$a_{12}$

$a_{13}$

$a_{14}$

$a_{15}$

Mezi jednotlivými prvky této haldy platí vztahy $a_1 \geq a_2$ a $a_1 \geq a_3$, dále $a_2 \geq a_4$ a $a_2 \geq a_5$, a tak dále, tedy $a_n \geq a_{2n}$ a $a_n \geq a_{2n+1}$.

V prvním kroku k prvkům $a_8$ a $a_9$ přidáme $a_4$ a seřadíme je podle daných vztahů. Dále k prvkům $a_4$ a $a_5$ přidáme $a_2$ a seřadíme je, pokud dojde k přehození, řadíme oddíl, ve kterém došlo ke změně.

Když takto sestavíme kupu, máme už prvek $a_1$ zařazený (je to nejvyšší prvek). Proto jej odsuneme na konec pole. Další nejvyšší je $\max (a_2, a_3)$, ten přejde na vrchol kupy a musíme opět upravit oddíl, ve kterém se změnil nejvyšší prvek. Pole máme seřazené, když se dostane poslední člen do čela kupy.