Heap sort

O(n log n)

Heap sort chápe pole jako binární haldu. Nejdřív ho přeuspořádá na max-haldu (každý rodič ≥ své děti), pak opakovaně prohodí kořen (maximum) na konec neseřazené části a nový kořen „prosype“ dolů, aby haldu obnovil. Běží v O(n log n) i v nejhorším případě a řadí na místě, bez rekurze.

Pole
Uprav vstup a stiskni Přehrát

Jak to funguje

  1. Postav max-haldu, aby největší hodnota byla v kořeni (index 0).
  2. Prohoď kořen s posledním neseřazeným prvkem — maximum je na místě.
  3. Prosyp nový kořen dolů a obnov vlastnost haldy.
  4. Zmenši haldu o jedna a opakuj, dokud není prázdná.

Pseudokód

1heapSort(a):                        # O(n log n)2  build a max-heap from a3  for end from n-1 down to 1:4    swap(a[0], a[end])               # max → its final spot5    siftDown(a, 0, end-1)           # restore the heap