Kas yra krūva?

Kepyklė (heap) yra speciali medžio struktūra duomenų, kuri atitinka kepyklės savybę. Ši savybė sako, kad bet kuriame viršūnėje, išskyrus šaknį, šios viršūnės raktas turi būti tam tikro santykio su jos tėvo reikšme. Yra du pagrindiniai kepyklės tipai:

• Maksimalioji kepyklė (Max-heap): Kiekvienos viršūnės raktas nėra mažesnis už jos vaikų raktus. Didžiausias elementas yra šaknyje.
• Minimalioji kepyklė (Min-heap): Kiekvienos viršūnės raktas nėra didesnis už jos vaikų raktus. Mažiausias elementas yra šaknyje.

Kepyklė dažniausiai įgyvendinama kaip masyvas, leidžiantis efektyviai pasiekti elementus ir atlikti operacijas. Ryšys tarp tėvo ir vaikų masyve yra toks:

• Elementui su indeksu i (pradedant nuo 0), jo kairysis vaikas yra indeksu 2i + 1.
• Jo dešinysis vaikas yra indeksu 2i + 2.
• Jo tėvas yra indeksu floor((i - 1) / 2).

Pagrindinės operacijos su kepykle:

• Įdėjimas (Insert): Naujo elemento pridėjimas. Laiko sudėtingumas O(log n), kur n yra elementų skaičius.
• Extract-Max / Extract-Min: Maksimalios (max-heap) arba minimalios (min-heap) elemento pašalinimas ir grąžinimas. Laiko sudėtingumas O(log n).
• Heapify (Kepyklės formavimas): Bet kurio masyvo pavertimas į kepyklę. Laiko sudėtingumas O(n).

Kepyklės naudojamos rūšiavimo algoritmuose (pvz., heapsort), prioritetų eilėse ir trumpiausių kelių paieškos algoritmuose (pvz., Dijkstra algoritmas).