Popište algoritmus vytvoření binární minimové haldy z neuspořádaného pole (HeapBuild) a uveďte jeho časovou složitost

Sestavení haldy

Haldu z n prvků lze sestavit voláním n krát operace HeapInsert

→ to pomocí Stirlingova vzorce O(log 2) + O(log 3) + O(log 4) + ….. + O(log n) = O (log (n!)) = O(n log n)

• jde to rychleji ⇒ HeapBuild()

HeapBuild

Myšlenka

1. Má-li prvek v dva syny l a p, kteří jsou kořeny podstromů tvořících korektní minimovou haldu, lze podstrom s kořenem ve v předělat na haldu BubbleDown(k(v))
2. Všechny vrcholy nejnižší hladiny haldy jsou triviálně korektní haldy o velikosti 1