Halda je binarny strom, kde plati, ze hodnota predchodcu musi byt mensia, ako hodnota jeho naslednika. Takze vieme, ze koren BS bude vzdy najnizsi prvok.
Haldu ukladame ako pole a plati, ze ak index prvku je k => 2k je lavy naslednik a 2k+1 je pravy naslednik, samozrejme, ak prvy index je 1.
- vkladat do haldy znamena prekopat pole, takze pri vlozeni musime preradit prvky - ak vlozime novy prvok, tak nam musi prebehnut haldou a najst si poziciu, podla toho musime prekopat aj nizsie urovne.
- vyberat znamena tiez prekopat prvky a preradit pole - teda vlastne nam staci prehodit najlavejsi prvok a prekopat tu cast stromu, kde sa deju zmeny
pri odstranovani korena, dame na miesto korena najposlednejsi prvok a nechame znovu zoradit. Ak vyberieme iny prvok, tak musime to iste spravit aj s tym prvkom.
haldu tvorime v poli, takze na zaciatku mame pole, ktora nema vlastnost byt haldou. na vystupe mame pole, ktore je haldou. pole - binarny strom - si rozdelime do podhald a kazdu zoradime, potom postupujeme vyssie a vyssie ... a potom mame hotovo :)
oprav koren = log(n)
vytvor haldu = O(n.log(n))
zorad haldu = theta(n.log(n))
