1  n := n+1; kasvata A:ta yhdellä lokerolla
2  i := n; j := ⌊i/2⌋
3  while j > 0 && A[j] < x do
4      A[i] := A[j]
5      i := j
6      j := ⌊i/2⌋
7  A[i] := x

Tehtävä:
Kekoon lisääminen

Lyhyt MathCheck-ohje (uuteen välilehteen)

Keko (englanniksi heap) on yksinkertainen mutta tehokas tieto­rakenne, johon voidaan lisätä alkioita milloin vain ja josta voidaan ottaa alkioita tärkeys­järjestyksessä. Keon alkiot voivat olla esi­merkiksi tehtäviä, jotka halutaan suorittaa kiirellisin ensin, tai risteyksiä, joihin navigointi­algoritmi on löytänyt reitit ja joista lähteviä teitä se tutkii se risteys ensin, johon on lyhin matka alku­peräisestä lähtö­paikasta. Keko on erittäin paljon nopeampi kuin tavallinen taulukko samassa tehtävässä.

Algoritmissa käytettävien merkintöjen selitykset voit katsoa tehtävän Puolitus­haku alusta.

Kekoesimerkki Kekoa varten on varattu taulukko A, josta on käytössä indeksit 1, …, n ja jota voidaan kasvattaa tarvittaessa. Oheinen kuva havainnollistaa kekoa siten, että numerot ovat A:n indeksejä ja kirjaimet ovat A:han talletettuja alkioita. Keon suuri tehokkuus perustuu alkioiden tallettamiseen erikoisessa järjestyksessä. Suurin alkio (tai jokin niistä, jos yhtä­suuria on monta) on lokerossa A[1]. Pätee A[2] ≤ A[1], A[3] ≤ A[1], A[4] ≤ A[2], A[5] ≤ A[2], A[6] ≤ A[3] ja niin edelleen alkioon A[n] saakka. Ilmaise tämä ominaisuus predikaattina. Kuvassa tämä ominaisuus näkyy siten, että viivaa ylös­päin mentäessä alkion arvo kasvaa tai säilyy ennallaan.
(a)
tai

Alkion x voi lisätä kekoon seuraavasti (sama algoritmi on oikealla alhaalla ja pysyy skrollatessa paikallaan):

1  n := n+1; kasvata A:ta yhdellä lokerolla
2  i := n; j := ⌊i/2⌋
3  while j > 0 && A[j] < x do
4      A[i] := A[j]
5      i := j
6      j := ⌊i/2⌋
7  A[i] := x

Kun keko on tyhjä, niin n = ja muutoin (täydennä n:n arvoa koskeva ehto). Siksi kun rivin 3 alkuun tullaan ensimmäisen kerran, i ≥ ja j = ⌊i/2⌋ i (lisää ≤, <, =, ≠, ≥ tai >).
tai

Kun rivin 3 alkuun tullaan uudelleen, sama i:tä ja j:tä koskeva väittämä pätee koska rivin 4 alussa pätee .
tai

Mistä syystä väittämä, jonka juuri osoitimme pätevän aina rivin 3 alussa, on tärkeä?
Se takaa, että A:ta ei indeksoida laittomasti.
Se takaa, että x sijoitetaan oikeaan lokeroon rivillä 7.
Se takaa, että algoritmi ei jää ikuiseen silmukkaan.
Se takaa, että (a):ssa verrataan oikeita alkioita keskenään.
tai

Kuten tehtävässä Insertion sort, suurimman osan algoritmin suoritusta yksi taulukon lokero on vapaa. Mikä on vapaan lokeron indeksi

rivin 2 alussa? tai
rivin 3 alussa? tai
rivin 5 alussa? tai
rivin 6 lopussa? tai
rivin 7 alussa? tai

Algoritmin hengen mukaista olisi kirjoittaa rivin 3 alun tilannetta kuvaamaan (a):n kaltainen predikaatti, joka jättää vapaan lokeron arvon vaille huomiota. Sellainen predikaatti olisi ikävä kyllä melko moni­mutkainen. Onneksi yhtä tapausta lukuun­ottamatta (a) pätee sellai­senaan sen ansiosta, mikä arvo vapaassa lokerossa oli ennen sen vapautumista. Ainoassa poikkeus­tapauksessa
i = . tai

Rivin 4 sijoituksessa vain yhden alkion arvo muuttuu, mutta se saattaa vaikuttaa jopa kolmeen (a):ssa tehtävään vertailuun. Kirjoita ensin se vertailu jossa indeksit ovat mahdollisimman pienet ja viimeiseksi se jossa ne ovat mahdollisimman suuret.

(b) A[] ≥ A[] tai
(c) A[] ≥ A[] tai
(d) A[] ≥ A[] tai

Miksi (b), (c) ja (d) säilyvät voimassa tai tulevat voimaan rivin 4 suorituksessa?(b)(c)(d)
A[i] säilyi ennallaan tai pieneni
A[i] säilyi ennallaan tai kasvoi
A[i] sai saman arvon kuin vertailun toinen osapuoli
tai

Mikä hoitaa edellä mainitun poikkeustapauksen kuntoon?
(b)(c)(d)
tai

Jotta meidän ei tarvitsisi käsitellä edellä mainittua poikkeustapausta erikseen, kuvittelemme, että rivin 2 loppuun on lisätty lause, jossa lokeroon A[] sijoitetaan
x
hyvin pieni arvo
hyvin suuri arvo.
Mekitsemme tätä lokeroa jatkossa symbolilla A[ö].
tai

Lisäyksen ansiosta (a) pätee aina kun ollaan rivin 3 alussa. Lisäys ei kuitenkaan todellisuudessa muuta algoritmin toimintaa, koska seuraava asia, mitä A[ö]:lle tehdään voi olla vain (valitse kaikki mahdolliset vaihto­ehdot)
A[ö] < x
A[ö] := A[j]
A[i] := A[ö]
A[ö] := x
tai

Vielä pitää varmistaa, että rivin 7 jälkeen ne (a):n mukaiset vertailut pätevät, joissa A[i] on osallisena. Käytä vastauk­sissasi muuttujina vain A ja i.

Verrataan ensin alkiota A[i] keon kuvassa lähimpänä ylempänä olevaan. Jos rivin 7 lopussa , niin paikka ei kuulu kekoon eikä (a) vertaa siihen. Muussa tapauksessa silmukan lopetus­ehto takaa, että kuten pitääkin.
tai

Jos silmukkaa ei kierretty yhtään kertaan, niin rivillä 7 i = , joten lokerot A[] ja A[] eivät kuulu kekoon. Muussa tapauksessa silmukassa siirrettiin x:n alta pois alkio, joka havaittiin rivillä 3 pienemmäksi kuin x. Kun ollaan rivillä 7, se on toinen äskeisen vastauksesi alkioista A[…] ja A[…]. Jos toinenkin näistä kahdesta kuuluu kekoon, se on (a):n vuoksi enintään yhtäsuuri kuin x:n alta siirretty, ja siksi pienempi kuin x.
tai

Siksi algoritmin lopussa ne (a):n mukaiset vertailut pätevät, joissa A[i] on osallisena.

Suurimman arvon löytäminen keosta on helppoa, koska se sijaitsee lokerossa A[].
tai

Kun suurin arvo on poistettu, keko voidaan korjata siirtelemällä vapautunutta paikkaa alaspäin samaan tapaan kuin lisäys­algoritmi siirteli vapaata paikkaa ylöspäin. Tämä on hieman moni­mutkaisempaa kuin lisäys­algoritmi, koska jos sekä A[2i] että A[2i+1] kuuluvat kekoon, pitää valita niistä suurempi sijoitettavaksi A[i]:n tilalle. Ennen siirtelyä kekotaulukon viimeinen alkio poistetaan keosta sijoittamalla n := n−1, ja lopuksi se kopioidaan vapaaseen paikkaan. Sen arvo otetaan huomioon vapaan paikan siirtelyn lopetusehdossa.

Kekoalgoritmeissa silmukka suoritetaan enintään suunnilleen log2 n kertaa, mikä on paljon vähemmän kuin taulukon selaaminen alusta loppuun suurimman alkion löytämiseksi olisi. Siksi keko on paljon nopeampi kuin tavallinen taulukko olisi.