Krūva

Straipsnis iš Vikipedijos, laisvosios enciklopedijos.

Krūva (Heap) tai 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ą)

Turinys 1 Operacijos 1.1 Įterpimas 1.2 Pašalinimas 2 Realizacija 3 Taikymas

[taisyti] Operacijos

[taisyti] Įterpimas

Norėdami įterpti elementą į krūvą, mes pridedame jį į žemiausią krūvos lygį ir sukeičiame vaiką su tevu, jei jie netentina 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 sąvybės, todėl sukeičiame jį su tėvu:

     11
    /  \
   5    15
  / \  /
 3  4 8

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

     15
    /  \
   5    11
  / \  /
 3  4 8

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

[taisyti] 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 sąvybę, 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 sąvybė yra labai susijusi su naudojama palyginimo operacija.

[taisyti] 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.

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ą.

[taisyti] 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.