Kas yra krūva programavimo kontekste ir kokios rūšys krūvų egzistuoja?

Heap — tai atminties sritis operatyviojoje atmintyje, naudojama dinamiškam atminties paskirstymui programos vykdymo metu.

Pagrindinės savybės:

• Atmintis aiškiai skiriama ir atlaisvinama programuotojo (arba šiukšlių rinkėjo).
• Nėra griežtos atminties blokų paskirstymo ir atlaisvinimo sekos.
• Atminties valdymas yra sudėtingesnis nei steke, gali sukelti fragmentaciją ir atminties nuotėkį.

Kaušų tipai (duomenų struktūrų kontekste):

• Dvinarioji kaušas (Binary Heap): medis, atitinkantis kaušo savybę. Kiekvienas mazgas (išskyrus šaknį) turi reikšmę mažesnę arba didesnę už tėvo reikšmę.
  • Min Heap: Tėvo reikšmė visada mažesnė arba lygi palikuonių reikšmėms. Mažiausias elementas yra šaknies vietoje.
  • Max Heap: Tėvo reikšmė visada didesnė arba lygi palikuonių reikšmėms. Didžiausias elementas yra šaknies vietoje.
• Binominių kaušas (Binomial Heap): binominių medžių kolekcija, atitinkanti tam tikras savybes. Užtikrina efektyvias sujungimo operacijas.
• Fibonacci kaušas (Fibonacci Heap): duomenų struktūra, naudojama algoritmuose, pvz., Dijkstro algoritmo. Užtikrina efektyvesnį amortizuotą laiko sudėtingumą kai kurioms operacijoms nei dvinarioji kaušas.
• Porinių kaušų (Pairing Heap): paprasta įgyvendinimo duomenų struktūra su geru amortizuotu laiko sudėtingumu.
• Kairioji kaušas (Leftist Heap): duomenų struktūra, palengvinanti efektyvų sujungimą. Svarbi savybė yra "rangas" arba "nulinio kelio ilgis", naudojamas greitam sujungimui.

Šie kaušų tipai naudojami įvairiuose algoritmuose, pvz., rūšiavimui (Heap Sort), prioritetinių eilių įgyvendinimui, trumpiausio kelio paieškos algoritmuose ir kt. Konkretus kaušo tipas pasirenkamas priklausomai nuo reikalingų operacijų ir jų laiko efektyvumo.