Binäärikeko (Binary Heap) on tietorakenne, johon olet tutustunut jo tietorakennekurssilla. Tässä tehtävässä jatkamme edellistä tehtävää toteuttamalla vielä yhden ominaisuuden lisää.
- Alkion prioriteetin päivitys binäärikeossa
Lue Web-CAT-ohje [täältä]. Tässä tehtävässä koodikattavuus lasketaan ns. branch coverage mitalla, joten jokaisen kun kaikki testit on ajettu, niin jokaisella koodirivillä on käyty kerran ja jokainen if-lauseen konditionaali on kerran ollut true ja false.
Palauta tehtävään jar-paketti jossa ovat muuttamasi luokat BinaryHeap.java, DataWithPriority.java sekä testiluokka, joka saat itse nimetä (nimen tulee päättyä sanaan Test jotta Web-CAT tunnistaa sen). Esim. MyHeapTest.java.
Joskus jonottaja voi saada kesken jonotuksen uuden vuoronumeron, jolla voi edetä keossa muutaman pykälän ylöspäin tai tippua huonommalle sijalle. Prioriteetin muuttumisen seurauksena keossa voi olla nyt kohta jossa kekoehto (solmun jonotusnumero on pienempi kuin sen lasten jonotusnumerot) on rikki. Korjaus tapahtuu samoilla algoritmeilla kuin lisäyksen tai poistonkin yhteydessä : solmu valuu joko ylöspäin tai alaspäin omalle paikalleen. Jälleen alkio liikkuu puussa maksimissaan O(log N) paikkaa ylös tai alas, joten operaatio on tehokas.
Ongelmana on kuitenkin että jos jonkin DataWithPriority-olion sisältämää prioriteettia muutetaan niin prioriteetin päivitys on tehokas vain jos tiedetään, missä paikassa kyseinen alkio keossa on. Muuten kekoa täytyisi vain käydä järjestyksessä läpi kunnes alkio löytyisi ja aloittaa liu'utus vasta sitten. Pahimmillaan tällöin katsottaisiin kaikki alkiot jolloin algoritmin tehokkuus olisikin O(N). On siis olennaista tietää jatkuvasti missä paikassa taulukossa alkio milloinkin on.
Käytännössä muutoksia tarvitaan sekä luokkaan DataWithPriority, että kekoluokan metodeihin insert ja deletemin. Tämän lisäksi toteutetaan tietenkin uusi metodi update(int location).
Tähän luokkaan kirjoitetaan tässä tehtävässä koodia joka tietää missä keossa tämä DataWithPriority-olio juuri tällä hetkellä on. Kirjoita luokkaan siis metodi, jota kutsumalla keko voi ilmoittaa DataWithPriority-oliolle insert:in yhteydessä mihin kekoon ja mihin paikalle se lisättiin ja deleteMin:iin koodi joka vastaavasti poistaa tuon tiedon.
Kun lisäksi muutat insert ja deleteMin metodeja niin että ne päivittävät jokaisen siirtyneen alkion sijainnin DataWithPriority-oliossa, niin olion paikka on jatkuvasti tiedossa.
Nyt voit toteuttaa DataWithPriority-luokkaan metodin updatePriority(), joka muuttaa k.o. olion sisältämän prioriteetin. Koska DataWithPriority tietää nyt mihin kekoon se kuuluu ja millä paikalla se on, voi se kutsua keon metodia update(int location), joka siirtää alkion uudelle paikalle.
DataWithPriority:n julkisen rajapinnan tulee sisältää vähintään seuraavat metodit :
Päivittää alkion prioriteetin ja hoitaa sen oikealle paikalleen keossa. Ei saa heittää poikkeusta vaikka alkio ei enää olisikaan keossa.
Jokin metodi, jota keko voi kutsua lisäyksen ja deleteMin:in yhteydessä kertoakseen mikä keko on kyseessä ja mihin paikkaan alkio laitettiin.
BinaryHeap:n julkisen rajapinnan tulee sisältää vähintään seuraavat uudet metodit (+vanhat):
Aloittaa prioriteettiarvon päivitystä seuraavan operaation jossa alkio liu'utetaan uudelle paikalleen.
Huomaa että koodin voi pitkälti ottaa copy-pastena edellisen kierroksen ratkaisusta. Jos haluat ratkaista tehtävän tyylillä (ei ole pakko :) ), kokeile saisitko insert ja deleteMin-metodien kanssa yhteisen koodin erilliseen metodiin. Vastaavasti edellisen kierroksen olisi voinut ratkaista käyttämällä update-metodia.
Omia metodeja saa (ja kannattaa) rakentaa tarpeen mukaan. Muista että Web-CAT vaatii että testitapauksesi kutsuvat näiden metodien koodirivejä ainakin kerran.