Šta je to hrpa?

Hajka (heap) je posebna struktura podataka u obliku stabla koja zadovoljava svojstvo hajke. Ovo svojstvo kaže da za svaku vrh, osim korena, vrednost ključa te vrha mora biti u određenom odnosu sa vrednošću ključa njenog roditelja. Postoje dve glavne vrste hajki:

• Maks-hajka (Max-heap): Vrednost ključa svake vrhova nije manja od vrednosti ključeva njenih dece. Najveći element nalazi se u korenu.
• Min-hajka (Min-heap): Vrednost ključa svake vrhova nije veća od vrednosti ključeva njenih dece. Najmanji element nalazi se u korenu.

Hajka se obično implementira kao niz, što omogućava efikasan pristup elementima i izvršavanje operacija. Veza između roditelja i dece u nizu je sledeća:

• Za element sa indeksom i (počinje od 0), njegov levi potomak nalazi se na indeksu 2i + 1.
• Njegov desni potomak nalazi se na indeksu 2i + 2.
• Njegov roditelj nalazi se na indeksu floor((i - 1) / 2).

Osnovne operacije nad hajkom:

• Insert (Umetanje): Dodavanje novog elementa. Vreme izvršenja O(log n), gde je n broj elemenata.
• Extract-Max / Extract-Min: Uklanjanje i vraćanje maksimalnog (u maks-hajki) ili minimalnog (u min-hajki) elementa. Vreme izvršenja O(log n).
• Heapify (Izgradnja hajke): Pretvaranje proizvoljnog niza u hajku. Vreme izvršenja O(n).

Hajke se koriste u algoritmima sortiranja (npr. heapsort), u redovima sa prioritetom, kao i u algoritmima za pronalaženje najkraćih puteva (npr. Dijkstrin algoritam).