Kurssiviikko 9¶

Itseopiskelu¶

Viikon aiheet: (i) Keko ja keon operaatiot, (ii) Keko taulukkona

Aiheiden opetusvideot ja kalvot:

Keko ja keon operaatiot¶

Kysymys 1

Kun käytetään max-kekoa, jossa on vähintään kaksi solmua,

lehden arvo voi olla suurempi kuin juuren arvo

on mahdollista, että jonkin solmun alipuu ei ole itse max-keko

koskaan ei voi tietää varmasti, missä suurin arvo sijaitsee

binääripuun pienin arvo sijaitsee jossain lehdessä

Kysymys 2

Keko on binääripuu. Mitkä seuraavista väittämistä ovat totta?

Binääripuun korkeus on mahdollisimman pieni käytetylle solmujen määrälle.

Kaikki lehdet ovat samalla syvyydellä.

On korkeintaan yksi solmu, jolla on täsmälleen yksi lapsi.

Parillisen syvyyden lehtien lukumäärän on oltava parillinen ja vastaavasti parittoman syvyyden lehtien lukumäärä on pariton.

Alimmalla syvyydellä jokaisen lehden on oltava vanhempansa ainoa lapsi.

Kysymys 3

Mitä tapahtuu lisättäessä uusi solmu max-kekoon?

Lisäämme aluksi uuden solmun lehdeksi. Jos uusi solmu on pienempi kuin juuri, uusi solmu pysyy lehtenä.

Korvaamme olemassa olevan juuren uudella solmulla. Sitten asetamme vanhan juuren lehdeksi mihin tahansa binääripuuhun ja lisäys on valmis.

Lisäämme uuden solmun aluksi lehdeksi. Niin kauan kuin uusi solmu on suurempi kuin sen vanhempi, solmu siirtyy binääripuussa ylöspäin.

Jos uusi solmu on suurempi kuin juuri, korvaamme juuren yksinkertaisesti uudella solmulla ja hävitämme vanhan juuren.

Kysymys 4

Missä tilanteessa max-keon heapify()-algoritmia käytetään?

kun solmulla on vain yksi lapsi ja vaadimme, että sillä on kaksi lasta

kun juurella on lapsi, joka on sitä suurempi

kun on olemassa lehti, joka on pienempi kuin sen vanhempi

kun kaikkien solmujen arvot ovat samat

Kysymys 5

Mitkä seuraavista väiteistä pätevät Build-Heap-algoritmille?

Toimiakseen oikein Build-Heap-algoritmin on tiedettävä, mitkä ovat syötteen binääripuun ei-lehtisolmut.

Build-Heap-algoritmi käsittelee binääripuun solmut käyttämällä esijärjestystä (preorder-järjestystä).

Build-Heap-algoritmi käynnistyy pienten kekojen kokoamisella. Näistä muodostuu asteittain suurempia kekoja, kunnes tuloksena on yksi keko.

Build-Heap toimii oikein vain silloin, jos sen syötebinääripuu on keko.

Kysymys 6

Mitä Heap-Extract-Max-algoritmi laskee?

Se etsii keon suurimman solmun ja lisää kekoon uuden lehden, joka on yhtä suuri kuin suurin solmu.

Joillekin positiivisille kokonaisluvuille \(k\) algoritmi muodostaa uuden max-keon, jolla on \(k\) suurimmat arvot syötekeosta. (Syöte \(k\) on korkeintaan syötekeon solmujen lukumäärä.)

Se poistaa syötteen max-keosta kaikki solmut, jotka ovat keon suurinta arvoa pienempiä.

Se hakee syötteen max-keosta suurimman arvon. Sen jälkeen se poistaa juuren ja suorittaa asianmukaiset laskut max-keon muodostamiseksi uudelleen.

Kysymys 7

Tarkastellaan seuraavaa neljää algoritmia: Build-Heap, Heap-Extract-Max, Heapify ja Heap-Insert. Oletetaan, että kunkin algoritmin syötteenä käytetyssä max-keossa solmujen lukumäärä on \(n\). Millä näistä neljästä algoritmista on tehokkuus, joka riippuu logaritmisesti koosta \(n\)?

Build-Heap ja Heap-Insert

Build-Heap, Heap-Extract-Max, ja Heap-Insert

Heap-Extract-Max, Heapify ja Heap-Insert

Build-Heap, Heap-Extract-Max ja Heapify

Keko taulukkona¶

Kysymys 1

Oletetaan, että binääripuun max-keko on tallennettu taulukkona \(A\). Oletetaan, että \(A[i]\) vastaa solmua \(x\). Mitkä seuraavista ovat totta?

Jos \(x\) on juuri, niin \(i\) on taulukon \(A\) ensimmäinen paikka.

Oletetaan, että \(x\) ei ole juuri. Ei ole olemassa funktiota, jonka tehokkuus on vakioaikainen, jolla voidaan laskea solmun \(x\) vanhemman paikka taulukossa \(A\).

Jos solmulla on kaksi lasta, niin on olemassa vakioaikaisia funktioita, joilla voidaan laskea solmun \(x\) lasten paikat taulukossa \(A\).

Jos max-keon solmujen lukumäärä on \(n\), oikeanpuoleisimman lehden paikka taulukossa \(A\) voi olla mitä tahansa välillä \(1\) ja \(n\).

Jos max-keon solmujen lukumäärä on \(n\), niin \(A[n]\) on max-keon pienin arvo.

Jos \(x\) on lehti, on vain kaksi mahdollisuutta alkiolle \(A[i+1]\). Joko \(A[i+1]\) vastaa toista lehteä tai \(A[i+1]\) ei vastaa mitään solmua, koska \(x\) on keon oikeanpuoleisin lehti.

Kysymys 2

Mitkä ovat Heapsort-algoritmin edut lukujen lajittelualgoritmina?

Lisätallennustilaa ei tarvita keon alkioden lajitteluun.

Kun käyttää Heapsort-algoritmia, ei tarvitse tietää keon alkioden todellista lukumäärää.

Sillä on sama iso-O-asymptoottinen tehokkuus kuin muilla nopeilla lajittelualgoritmeilla, kuten Mergesort.

Heapsort-algoritmia käytettäessä testataan vakioaikaisesti, onko keko jo täysin lajiteltu vai ei.

Kun käyttää Heapsort-algoritmia, ei koskaan tarvitse kertoa tai jakaa kahdella, mikä tekee Heapsort-algoritmista erittäin nopean.

Kysymys 1

Muotoile kurssin kannalta keskeinen kysymys, johon tämän viikon videot antavat vastauksen.

Kysymys 2

Minkä videon aiheesta pitäisi erityisesti keskustella keskustelutilaisuudessa?

Keko binääripuuna

Keon operaatiot ja niiden tehokkuudet

Keko taulukkona

Heapsort

Kysymys 3

Oliko videoiden sisällössä jotain erityisen vaikeaa? Entä mielenkiintoista? Jotain josta haluaisit oppia lisää?

Lisäinformaatiota aiheesta:

Tyypillisesti prioriteettijono toteutetaan binääripuukekona. Vaihtoehtoinen tietorakenne, jota voidaan käyttää prioriteettijonona, on binomipuukeko

Viikko09 - Sanasto

Viikkoharjoitusten palautettavat kotitehtävät¶

Tällä viikolla palautettavat tehtävät

Kurssiviikko 9¶

Itseopiskelu¶

Keko¶

Keon operaatiot¶

Keon operaatioiden tehokkuus¶

Keko taulukkona¶

Suunnitteluperiaate Muunna-ja-hallitse, kekolajittelu¶

Keko ja keon operaatiot¶

Keko taulukkona¶

Viikkoharjoitusten palautettavat kotitehtävät¶