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.
![]() |
||||||||||||||
![]() |
![]() |
|||||||||||||
![]() |
![]() |
![]() |
![]() |
|||||||||||
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
|||||||
Mezi jednotlivými prvky této haldy platí vztahy a
, dále
a
, a tak dále, tedy
a
.
V prvním kroku k prvkům a
přidáme
a seřadíme je podle daných vztahů. Dále k prvkům
a
přidáme
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 zařazený (je to nejvyšší prvek). Proto jej
odsuneme na konec pole. Další
nejvyšší je
, 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.