Kurssiviikko 9

Itseopiskelu

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

Aiheiden opetusvideot ja kalvot:

Keon operaatioiden tehokkuus

Suunnitteluperiaate Muunna-ja-hallitse, kekolajittelu

Keko ja keon operaatiot

Kun käytetään max-kekoa, jossa on vähintään kaksi solmua,
Keko on binääripuu. Mitkä seuraavista väittämistä ovat totta?
Mitä tapahtuu lisättäessä uusi solmu max-kekoon?
Missä tilanteessa max-keon heapify()-algoritmia käytetään?
Mitkä seuraavista väiteistä pätevät Build-Heap-algoritmille?
Mitä Heap-Extract-Max-algoritmi laskee?
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\)?

Keko taulukkona

Oletetaan, että binääripuun max-keko on tallennettu taulukkona \(A\). Oletetaan, että \(A[i]\) vastaa solmua \(x\). Mitkä seuraavista ovat totta?
Mitkä ovat Heapsort-algoritmin edut lukujen lajittelualgoritmina?
Muotoile kurssin kannalta keskeinen kysymys, johon tämän viikon videot antavat vastauksen.
Minkä videon aiheesta pitäisi erityisesti keskustella keskustelutilaisuudessa?
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