Krūva

Šiam straipsniui ar jo daliai trūksta išnašų į patikimus šaltinius. Jūs galite padėti Vikipedijai pridėdami tinkamas išnašas su šaltiniais.

Šio puslapio ar jo dalies stilius neatitinka Vikipedijos kalbos standartų. Jei galite, pakoreguokite stilių, kad tiktų enciklopedijai. Tik tada bus galima ištrinti šį pranešimą.

Krūva (angl. heap) - panaši į dvejetainį paieškos medį informatikoje naudojama duomenų struktūra.

Krūva galėtų būti vadinama dvejetainiu paieškos medžiu su dviem sąlygomis:

1. Tai visada yra užbaigtas (pilnas ir visi lapai yra h arba h-1 aukštyje) medis
2. Kiekvienas viršūnės vaikas tenkina pasirinktąją palyginimo operaciją su viršūne (negalioja sąlyga apie kairįjį ir dešinįjį dvejetainio medžio vaiką)

Operacijos

Įterpimas

Įterpimas į krūvą

Norėdami įterpti elementą į krūvą, mes pridedame jį į žemiausią krūvos lygį ir sukeičiame vaiką su tėvu, jei jie netenkina mūsų krūvos sąlygos. Tokio algoritmo sudėtingumas yra O (log n)

Pavyzdžiui, mūsų krūvoje gali būti krūvoje apibrėžta savybė, kad šaknis yra didesnė ar lygi vaikui.

     11
    /  \
   5    8
  / \  /
 3  4 X

Mes norime įterpti 15 į krūvą. Sakykime, 15 bus X pozicijoje. Įterpę palyginame 15 su tėvu – deja, jis neatitinka mūsų krūvos savybės, todėl sukeičiame jį su tėvu:

     11
    /  \
   5    15
  / \  /
 3  4 8

Palyginame dar kartą – medis vis dar netenkina mūsų sąlygos (11 < 15). Sukeičiame ir gauname:

     15
    /  \
   5    11
  / \  /
 3  4 8

Šitoks medis mūsų sąlygą tenkina.

Pašalinimas

Pašalindami, mes pakeičiame nereikalingą elementą, paskutiniu žemiausio lygio lapu ir tikriname krūvos teisingumą. Jei mūsų krūva neatitinka reikalavimo, sukeičiame viršūnę su vaiku, kol negausime mus tenkinančios krūvos.

Pavyzdžiui, mūsų krūvoje gali būti krūvoje apibrėžta savybė, kad šaknis yra didesnė ar lygi vaikui.

     11
    /  \
   5    8
  / \  
 3  4 

Pašaliname 11 ir pakeičiame 4

      4
    /   \
   5     8
  / 
 3  

Kaip matome, medis neatitinka reikalavimų, todėl pakeičiame 4 jo (labiausiai mūsų krūvos savybę atitinkančiu) vaiku

      8
    /   \
   5     4
  / 
 3

Toks medis tenkina mūsų reikalavimus.

Reikia pabrėžti, kad krūvos savybė yra labai susijusi su naudojama palyginimo operacija.

Realizacija

Būtų labai sunku realizuoti krūvą dvejetainiu medžiu, nes, kaip matėme, įterpimo ir pašalinimo operacijoms reikalinga žinoti, koks yra paskutinis lapas.

Realizacijos masyvu pavyzdys

Patogiau ir populiariau krūvą realizuoti masyvu, saugant elementus tokia tvarka: šaknis yra pirmas elementas, toliau: kairysis šaknies vaikas, dešinysis šaknies vaikas, kairiojo šaknies vaiko kairysis vaikas… Jei, pavyzdžiui, viršūnė turi tik kairįjį vaiką, laukelis sekantis paskui tą vaiko elementą paliekamas tuščias. Taip realizuotoje krūvoje labai lengvai galima surasti paskutinį elementą bei įterpti naują.

Taikymas

Būdas, kuriuo duomenys yra organizuoti krūvoje, leidžia efektyviai realizuoti prioritetų eilės operacijas. Ši duomenų struktūra taip pat naudojama efektyviame krūvos rikiavimo algoritme.