1. Johdanto ja määritelmiä
2. Keon esittäminen taulukkona
3. Minimikeko vs. maksimikeko
4. Alkion lisääminen
5. Suurimman alkion poistaminen
6. Kekoehdon ylläpito (maksimikeko)
7. Keon rakentaminen
8. Kekojärjestäminen
9. Keon korkeus

7. Keon rakentaminen

Keon rakentaminen lineaarisessa ajassa (bottom-up heap construction, build heap)

Keko voidaan tuottaa aluksi mielivaltaisessa järjestyksessä olevasta taulukosta myös lineaarisessa ajassa (ts. vaihtamalla alkioiden paikkoja, taulukosta saadaan keko käyttämällä korkeintaan kn+c vaihtoa, jossa n on taulukossa olevien alkioiden lukumäärä ja k ja c ovat pieniä vakioita).

Menetelmässä tarkastellaan aluksi puun kahta alimmaista tasoa ja organisoidaan kaikki niillä olevat pienet alipuut keoiksi josta edetään seuraavaksi ylemmälle tasolle aina koko puun juureen saakka. Tämä tehdään käymällä läpi alipuiden juurisolmut lopusta alkuun. Olkoon kyseessä minimikeko. Jokaisen alipuun juuren kohdalla juuren prioriteettia verrataan aina pienempään lapseen (ensin siis vertaillaan lapsia keskenään, jotta voidaan päätellä kumpi on pienempi). Tarvittaessa - eli jos lapsi on pienempi kuin isä - alkiot vaihtavat paikkaa. Eteen saattaa tulla tilanne, jossa taso alaspäin vaihdettu isäsolmu on edelleen suurempi kuin pienempi sen uusistakin lapsista. Tällöin em. prosessi toistetaan tälle pienemmälle keolle kuten aikaisemmin (ja solmu saatetaan vaihtaa puussa tällä tavoin jopa lehteen saakka). Kun kaikki tasot on käyty läpi juureen saakka, koko rakenne on organisoitu keoksi.

Seuraavassa on esitetty keonrakennusalgoritmi maksimikeolle. Minimikeon tapauksessa kutsuttaisiin rivillä 2 MIN-HEAPIFY(A, i) algoritmia, jonka toiminta on analoginen MAX-MEAPIFY:n toiminnalle.

Taulukosta A[0..n-1] tehdään keko, jossa n = heap-size[A].

Käytetään toistuvasti rutiinia Max-Heapify

• Max-Heapify-algoritmia tarvitsee kutsua vain alkioille A[⌊n/2⌋-1], A[⌊n/2⌋-2], ..., A[0], koska
• loput alkiot ovat puun lehtiä ja
• ne muodostavat kukin 1-alkioisen keon (joille triviaalisti kekoehto on jo voimassa). Voidaan todistaan, että BUILD-MAX-HEAP-algoritmin aikakompleksisuus on O(n).

  Tehtäviä: Keon muodostuminen

  Tehtävä Muodosta oheisesta taulukosta binäärikeko lineaarisessa ajassa toimivalla BuildHeap-algoritmilla (joka tunnetaan myös nimillä Fixheap ja Bottom-Up Heap Construction). Kekoehto on "isä suurempi kuin lapsensa". Ohjeet Tehtävässä kahden avaimen (lähde- ja kohdeavain) paikka voidaan vaihtaa vetämällä ja pudottamalla lähdeavain kohdeavaimen päälle. Huomaa, että tehtävässä binäärikeko on esitetty sekä taulukkona että binääripuuna. Molemmat esitysmuodot edustavat yhtä ja samaa rakennetta ja tehtävän voi ratkaista muokkaamalla kumpaa näkymää tahansa. Build-Heap Algorithm 4 Build-Max-Heap(A) for i ← heap-size[A]/2-1 downto 0 do Max-Heapify (A, i) end for Algorithm 2 Max-Heapify(A, i) l ← Left-child-index(i) r ← Right-child-index(i) if l < heap-size[A] and A[l] > A[i] then greatest ← l else greatest ← i end if if r < heap-size[A] and A[r] > A[greatest] then greatest ← r end if if greatest ≠ i then Swap(A[i],A[greatest]) Max-Heapify(A, greatest) end if