Medis, sudėtas į masyvą

Krūva yra medis, sudėtas į masyvą. Ne medis su masyvu greta — pats masyvas IR YRA medis.

Kur dingo rodyklės

Vienuoliktoje ir dvyliktoje pamokose mazgas turėjo dvi rodykles, o vaikai buvo ten, kur rodyklė nukreipia. Čia jų nėra, nes vaikų vieta apskaičiuojama:

mazgui, esančiam indekse i:
    tėvas      (i−1)/2
    kairysis   2i+1
    dešinysis  2i+2

indeksas:  0   1   2   3   4   5   6
reikšmė:  12  19  15  41  22  17  33

                12
              /    \
            19      15
           /  \    /  \
         41   22  17   33

Tas pats medis, nupieštas dviem būdais. Antrasis yra tiesiog pirmojo eilutė paeiliui, lygis po lygio.

Kaina rodyklėms: 0 baitų. Vienuoliktos pamokos mazgas kainavo 88 baitus, dvyliktos — 96, ir kiekvienas gulėjo krūvoje ten, kur pakliuvo. Čia visi elementai guli gretimai, vienas paskui kitą, ir procesorius juos ištraukia paketais.

Vienuoliktoje pamokoje pamatavai, ką kainuoja išbarstytos rodyklės: tie patys 5000.5 palyginimo ir 4.5 karto daugiau laiko. Čia ta pati pastaba veikia priešinga kryptimi.

Krūvos savybė

Kiekvienas tėvas ne didesnis už savo vaikus.

Viskas. Nė žodžio apie kairę ir dešinę — tarp brolių tvarkos NĖRA. Aukščiau 19 > 15, ir tai visiškai teisinga krūva.

Iš to plaukia vienintelis dalykas, kurį krūva žino: mažiausias elementas yra a[0]. Visada. Be paieškos, be palyginimo. Ir daugiau ji nežino nieko — penktas žingsnis apie tai, kodėl to pakanka.

Įterpimas: kilk aukštyn

Push(item):
    pridėk item masyvo gale
    i ← len(a) − 1
    kol i > 0:
        p ← (i−1)/2
        c.Hit()
        jei a[p] ≤ a[i]: baik        // tėvas ne didesnis — tvarka
        sukeisk a[p] ir a[i]
        i ← p

Naujas elementas įdedamas į vienintelę laisvą vietą ir kyla, kol jo tėvas tampa ne didesnis. Kelias iki šaknies yra log2 n ilgio, tad O(log n).

Viršūnės ėmimas: leiskis žemyn

Pop():
    viršus ← a[0]
    a[0] ← paskutinis elementas; sutrumpink masyvą
    i ← 0
    ciklas:
        rask mažiausią iš a[i], a[2i+1], a[2i+2]     // 2 palyginimai
        jei mažiausias yra a[i]: baik
        sukeisk juos; i ← mažiausiojo indeksas
    grąžink viršų

Paskutinis elementas keliauja į šaknį — tai vienintelis būdas nepalikti masyve skylės — ir leidžiasi, kol abu vaikai tampa ne mažesni.