1

(a)

Uusi alkio lisätään keon seuraavaan vapaaseen kohtaan.
Alkiota nostetaan ylöspäin keossa, kunnes se on saavuttanut
oikean kohdan eli sen yläpuolella on pienempiä alkioita
ja alapuolella on suurempia alkioita.

Tehtävän minimikeko puumuodossa ja taulukkomuodossa:

         3
       /   \
     5       7
    / \     / \
  21    9 10   13
 / \   / \
25 23 18 15    

--------------------------------------------------------
|  3 |  5 |  7 | 21 |  9 | 10 | 13 | 25 | 23 | 18 | 15 |
--------------------------------------------------------

(b)

Funktiot f1, f2, f4 ja f6 ovat hajautusfunktioita.
Funktiot f3 ja f5 eivät ole hajautusfunktioita,
koska ne saattavat antaa eri arvon samalla avaimella.

Funktio f1 antaa jokaiselle sanalle saman hajautusarvon.
Niinpä se on käytännössä hyvin huono hajautusfunktio.
Esim. sanat "aakkonen" ja "öylätti" saavat saman hajautusarvon.

Funktio f2 antaa saman hajautusarvon sanoille,
joiden kirjainten määrä on sama. Funktio on nopea laskea,
mutta se antaa monelle sanalle saman hajautusarvon.
Esim. sanat "jono" ja "pino" saavat saman hajautusarvon.

Funktio f4 antaa saman hajautusarvon sanoille,
joiden ensimmäinen kirjain on sama. Funktio on nopea laskea,
mutta se antaa monelle sanalle saman hajautusarvon.
Esim. sanat "aalto" ja "apina" saavat saman hajautusarvon.

Funktio f6 antaa saman hajautusarvon mm. sanoille,
jotka ovat anagrammeja eli sisältävät jokaista kirjainta
yhtä monta kertaa. Funktio on parempi kuin muut tässä
olevat funktiot mutta siinäkin esiintyy paljon törmäyksiä.
Esim. sanat "asia" ja "aisa" saavat saman hajautusarvon.

(c)

Ks. materiaalin sivut 295-297