Krūva

Straipsnis iš Vikipedijos, laisvosios enciklopedijos.
Peršokti į: navigaciją, paiešką

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[taisyti | redaguoti kodą]

Įterpimas[taisyti | redaguoti kodą]

Į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[taisyti | redaguoti kodą]

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[taisyti | redaguoti kodą]

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[taisyti | redaguoti kodą]

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.