Popište algoritmus HeapSort, diskutujte jeho konečnost a korektnost a uveďte jeho časovou složitost.

Halda umožňuje zkonstruovat rychlý algoritmus pro řazení

• Tento algoritmus se nazývá HeapSort

HeapSort

• pomocí haldy lze třídit

Myšlenka

1. Posloupnost, kterou chceme setřídit vložíme do pole
2. Na toto pole zavoláme HeapBuild
3. Poté n-krát zavoláme HeapExtractMin a vrácené hodnoty vypíšeme do výstupního pole

Podle analýz zmíněných v předchozích veta otázkách má HeapSort časovou složitost O(n) + O(n log n) = O(n log n)

Algoritmus HeapSort, lze realizovat in-place, ****tedy bez použití extra paměti na uložení zkonstruované haldy