Heap sort

Průběh cvičení

Zopakovali jsme si, co to je max-halda a jak jejích vlastností využívá heap-sort k rychlejšímu třídění.

Ukázali jsme si, jak opravit haldu se špatným vrcholem, když je zbytek struktury v pořádku (max-heapify). Poté jsme se podívali, jak tohoto postupu lze využít pro vybudování haldy z libovolného pole (build-max-heap) a nakonec jakým způsobem tyto myšlenky kombinuje heap-sort při třídění polí.

Zamysleli jsme se i nad složitostí všech těchto procedur i celého heap-sortu. Vše jsme si ukázali na příkladech.

Úkol

1. Implementujte heap-sort v jazyce C/Python.