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 heapsort 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 k procvičení

1. Implementujte heap sort v jazyce C/Pythonu.