Tietorakenteet / syksy 2004 / 2. välikoe / 2. tehtävä

(a) ja (b) ks. moniste s. 152-3, toisin kuin monisteen tapauksessa nyt
           kyseessä minimikeko!

(c) esim:       3
              /   \
            5       6
           / \     / \
          9  10   17 19
         / \
       22   84

(d) change-key(i,k)
      if k<key[i] then // avain pienenee, vietävä ylöspäin
         while k<key[parent[i]] and i>i do
            k[i] <- key[parent[i]]
            i <- parent[i]
         key[i] <- k
      else // ehkä suurenee, vietävä alaspäin
         key[i] <- k
         heapify(i)

     heapify-toteutus, ks. moniste s. 154

(e) aikav:
      jos vaihd. juurialkioon iso arvo, se voi pahimmassa tapauksessa
      aiheuttaa heapify-kutsuja puun kork verran, ja koska heapifyn
      jok. instanssi vie vakioajan ja n solmuisen kekopuun korkeus 
      O(log n), on tamä tapaus aikavaativuudeltaan O(log n)
 
      jos vaihd. lehteen pieni arvo, voidaan se pahimmassa tapauksessa 
      joutua viemään puun korkeuden verran ylöspäin, ja koska jokainen 
      tasonnosto vie vakioajan, on tamäkin tapaus aikavaativuudeltaan O(log n)

      eli operaation aikavaativuus O(lon n) missä n keossa olevien
      alkioiden määrä
 
    tilav:
      jos vaihd. juurialkioon iso arvo, se voi pahimmassa tapauksessa
      aiheuttaa heapify-kutsuja puun kork verran, ja koska heapifyn
      jok. instanssi vie vakiotilan ja n solmuisen kekopuun korkeus 
      O(log n), on tamä tapaus tilavaativuudeltaan O(log n)

      alkion ylöspäin vienti ei vaadi tilaa sillä kyseessä toistolause

      siis operaation tilavaativuus on myös O(lon n) missä n keossa olevien
      alkioiden määrä

(e)   84 -> 11 ei muutosta!


                3
              /   \
            5       6
           / \     / \
          9  10   17 19
         / \
       22   11

       3 -> 55

                55
              *    \
            5        6
           / \      / \
          9  10    17 19
         / \
       22   11

         heapify(1)

                5
              /   \
            55      6
           * \     / \
          9  10   17 19
         / \
       22   11

         heapify(2)

                5
              /   \
            9       6
           / \     / \
         55   10  17 19
        /  *
       22   11

          heapify(4)

                5
              /   \
            9       6
           / \     / \
         11   10  17 19
        /  \
       22   55

pisteytys:

(a), (b) ja (c) 1p
(d), (e) ja (f) 2p

yleisiä huomioita:
- a-c muuten ok mutta kyseessä maksimikeko, a-c tuottivat yht 2p
- heapify määrittelemättä eikä edes sen toimintaperiaatetta kerrottu -1p
- d:ssä vain "toinen suunta" huomioitu -1p
- ei algoritmia => vaativuusanalyys 0p
- ei algoritmia mutta simulaatio oikein -1p 
- aikavaativuuden toteaminen ilman "analyysiä" 0p