V tomto texte si budeme rozprávať o haldách: jednoduchých stromových dátových štruktúrach, ktoré nám umožňujú udržiavať si údaje "tak trochu usporiadané". Ukážeme si, ako sa to robí a na čo je to dobré.
Počas vysvetľovania sa v tomto texte budú zjavovať obrázky rôznych stromov. Nebojte sa ich. Nebude ich treba implementovať. Keď sa úspešne dostaneme až na koniec našich úvah, ukáže sa, že nám bude stačiť jedno obyčajné pole.
Naším hlavným cieľom v tomto článku bude efektívna implementácia takzvanej prioritnej fronty. Toto je dátová štruktúra, ktorá vie efektívne robiť dve operácie:
push(prvok, priorita): vlož nový prvok a nastav mu konkrétnu prioritupop(): vyber prvok, ktorý má spomedzi všetkých aktuálne uložených prvkov najväčšiu priorituPrioritnú frontu si teda vieme predstaviť ako čakáreň na pohotovosti. Postupne nám prichádzajú pacienti, každý s inou prioritou -- niekto je na tom lepšie, niekto horšie. No a vždy, keď sa ordinácia uvoľní, ošetrujúci lekár do nej zoberie pacienta s najväčšou prioritou, teda toho, kto najakútnejšie potrebuje ošetrenie.