Algoritmid ja andmestruktuurid: puud, kuhjad (0)

1
Kuhjad
2
Olemus
Kuhi  (ingl  heap ) on puu või mets, kus:
– igas tipus on üks võtmega kirje,  kusjuures  võtmed on omavahel
võrreldavad;
– kehtib nn kuhjatingimus (ingl heap property): iga tipu kirje
võti on vähemalt niisama suur kui tema suvalise alluva kirje võti.
3
Märkusi
• Tihti kasutatakse ka kuhje, kus kuhjatingimuses nõutakse vastupi-
dist järjestust: iga tipu kirje võti on ülimalt niisama suur kui tema
suvalise alluva kirje võti (nn pöördkuhi (ingl min-heap)).
• Kasutatakse mitut kuhjaliiki, millest igaühe puhul nõutakse lisaks
tingimusi puu struktuuri kohta.
4
Eesmärk
Kuhjad on mõeldud puhuks, kui ühtedeks põhioperatsioonidest on suu-
rima (või vähima) võtmega kirje leidmine ja eemaldamine.
Lisaks neile peab olema võimalik odavalt  sooritada   kirjete  lisamist.
– Sobivad seega eelistusjärjekorra realiseerimiseks.
1
Kahendkuhjad
5
Kahendkuhjad
1
Kahendkuhjad
6
Invariant
Kahendkuhja (ingl  binary  heap) puhul nõutakse
– kuhjatingimust
– ja et tegu oleks kompaktse kahendpuuga.
1
Kahendkuhjad
7
Kuhjatingimuse rekurrentne määratlus
Kahendpuu  rahuldab  kuhjatingimust, kui kas ta on tühi või
– juure kirje võti on maksimaalne üle kogu puu (pöördkuhja puhul
minimaalne), ja
– mõlemad harud rahuldavad kuhjatingimust.
1
Kahendkuhjad
8
Ülekanduvus alampuudele
Kahendkuhja iga alampuu on kahendkuhi.
1
Kahendkuhjad
9
Esitus
Eeldame, et
– iga tipu puhul on  ajaga  O(1) kättesaadav tema ülemus, kui see
leidub (lisaks muidugi alluvatele).
– ajaga O(1) on teostatav viimase taseme viimase tipu likvideeri-
mine ja uue tipu lisamine sinna.
Kui kahendkuhja esitamiseks kasutada kompaktse kahendpuu esitust
massiivina ja kasutada lisaks üht välja kirjete reaalse arvu hoidmiseks,
siis need tingimused on täidetud, välja arvatud uue tipu lisamine juhul,
kui  massiiv  on täis.
1
Kahendkuhjad
10
1.1
Operatsioonid
Operatsioonid
1
Kahendkuhjad
11
1.1
Operatsioonid
Lisamisülesanne
Lisada antud kahendkuhja antud kirje.
–  Sisend : kahendkuhi, kirje.
1
Kahendkuhjad
12
1.1
Operatsioonid
Lahendus
Lisatakse endisi tippe puutumata puule uus tipp, nii et puu jääb kom-
paktseks kahendpuuks;
kirjutatakse  uus kirje uude tippu;
viiakse uus kirje mullina mööda puustruktuuri üles oma kohale, nii et
ka kuhjatingimus  taastub .
1
Kahendkuhjad
13
1.1
Operatsioonid
Mullina ülesviimine
Mullina ülesviimine (ingl  bubble -up):
kui kirje on tipu ülemuse kirje suhtes  vales  järjestussuhtes, siis
–  vahetatakse  ta ülemuse  kirjega ,
– ja viiakse ta omakorda sealt mullina üles.
1
Kahendkuhjad
14
1.1
Operatsioonid
Keerukus
Eeldusel, et võrdlusoperatsioonid ja vahetused on O(1), toimub lisa-
mine
– halvimal juhul keerukusega O(log n),
– parimal ja keskmisel juhul keerukusega O(1),
kus n tähistab  kuhja  tippude arvu.
1
Kahendkuhjad
15
1.1
Operatsioonid
Eemaldamisülesanne
Eemaldada kahendkuhjast suurima võtmega kirje.
– Sisend: kahendkuhi.
– Väljund: kuhja vähima võtmega kirje, kui kuhi just tühi ei olnud.
1
Kahendkuhjad
16
1.1
Operatsioonid
Lahendus
Kui puu on tühi, siis lõpetatakse ebaõnnestumisega.
Muidu:
– likvideeritakse puu viimase taseme viimane tipp;
– kirjutatakse seal olnud kirje puu juurtippu;
– viiakse juurtipu kirje mullina alla, nii et taastub kuhjatingimus;
– tagastatakse juurtipus algselt olnud kirje.
1
Kahendkuhjad
17
1.1
Operatsioonid
Mullina allaviimine
Mullina allaviimine (ingl bubble-down):
kui kirje on oma mõne alluvaga vales järjestussuhtes, siis
– vahetatakse ta tipu selle alluva kirjega, mille võti on suurem
(pöördkuhja puhul väiksem);
– viiakse ta oma uuelt positsioonilt omakorda alla.
1
Kahendkuhjad
18
1.1
Operatsioonid
Keerukus
Eeldusel, et võrdlusoperatsioonid ja vahetused on O(1), toimub suuri-
ma võtmega kirje eemaldamine
– halvimal ja keskmisel juhul keerukusega Θ(log n),
– parimal juhul keerukusega Θ(1).
1
Kahendkuhjad
19
1.1
Operatsioonid
Kuhjaparandused
Ühe vales positsioonis asuva kirje mullina üles- või allaviimist nime-
tatakse kuhjaparanduseks.
– Need aitavad ka juhul, kui ühes kindlas positsioonis kirje võti
muutub.
1
Kahendkuhjad
20
1.1
Operatsioonid
Massiivi täitumise probleem
Kui kahendkuhi esitada massiivina, siis tasub massiivi suurus võtta va-
ruga, et täitumist tuleks ette küllalt harva.
Nt võtta massiiv pikkusega 2n − 1 (täieliku kahendpuu suurus) ja kui
ta saab täis, siis võtta uus massiiv pikkusega 2n+1 − 1 jne.
– Siis tipu juurdetekitamine viimase taseme lõppu on keskmise
keerukusega O(1).
1
Kahendkuhjad
21
1.2
Järjestamise kuhjameetod
Järjestamise kuhjameetod
1
Kahendkuhjad
22
1.2
Järjestamise kuhjameetod
Kuhjastamine
Ülesanne: tekitada kahendkuhi, milles oleksid  parajasti  samad  kirjed
nagu antud järjendis.
– Sisend: järjend.
– Väljund:  samade  kirjetega kahendkuhi.
1
Kahendkuhjad
23
1.2
Järjestamise kuhjameetod
“Jaga ja valitse” lahendusalgoritm
Esiteks tekitada kompaktne kahendpuu, milles oleksid parajasti samad
kirjed nagu antud järjendis. (St paigutada tipud kompaktse kahendpuu
struktuuri järgi.)
Seejärel muuta puu kuhjaks “jaga ja valitse” strateegiaga:
– muuta kuhjaks kumbki haru samal viisil;
– viia juure kirje mullina alla.
1
Kahendkuhjad
24
1.2
Järjestamise kuhjameetod
Järjestikalgoritm
Luua tühi kuhi;
lisada järjendi kirjed järjekorras sinna.
1
Kahendkuhjad
25
1.2
Järjestamise kuhjameetod
Keerukus
Kui n tähistab kirjete arvu, siis järjendi pealt kuhja tekitamise keerukus
on
– järjestikalgoritmi puhul halvimal juhul Θ(n log n), keskmisel ja
parimal juhul Θ(n);
– “jaga ja valitse” algoritmi puhul alati Θ(n).
1
Kahendkuhjad
26
1.2
Järjestamise kuhjameetod
“Jaga ja valitse” algoritm massiivi puhul
• Eeltöö — kompaktse kahendpuu struktuuri loomine — on triviaal-
ne.
– Etteantud massiivi võib algusest peale käsitleda nii, nagu ta väl-
jendaks kompaktset kahendpuud.
∗ Positsioonid massiivis määravad alluva-ülemuse suhted ära.
• Põhitöö — järjest suuremate alampuude muutmine kuhjaks — on
teostatav tsükliga.
– Läbime massiivi tagurpidi, rakendades iga elemendi juures kirje
allaviimist.
1
Kahendkuhjad
27
1.2
Järjestamise kuhjameetod
Järjestamine
Järjend kuhjastatakse, ning
tsüklis eemaldatakse kuhjast suurima võtmega kirje ja lisatakse looda-
vasse järjendisse suunaga lõpust alguse poole, kuni kuhi saab tühjaks.
– Meetod on ebastabiilne.
1
Kahendkuhjad
28
1.2
Järjestamise kuhjameetod
Keerukus
Järjestamise kuhjameetodi keerukus on O(n log n).
2
Binomiaalkuhjad
29
Binomiaalkuhjad
2
Binomiaalkuhjad
30
Invariant
Binomiaalkuhja (ingl binomial heap) puhul nõutakse
– kuhjatingimust (pööratud järjestuse suhtes)
– ja et tegu oleks binomiaalmetsaga (metsaga, kus puudeks on paa-
rikaupa erinevat järku binomiaalpuud).
2
Binomiaalkuhjad
31
Ülekanduvus alamstruktuuridele
Binomiaalkuhja igast tipust lähtuva puu harude mets on binomiaalku-
hi.
2
Binomiaalkuhjad
32
Eesmärk
Lisaks kahendkuhjas defineeritud operatsioonidele lubab binomiaal-
kuhjastruktuur ka kuhjade kiiret ühendamist.
2
Binomiaalkuhjad
33
Esitus
Sobib kasutada seotud paigutust (nagu ikka metsal). Üldiselt  piisab
puudes viitadest alla (alluvatele/harude metsale).
– Kui vaja arvestada  muutuvate  võtmetega, siis tuleks efektiivsuse
huvides puudes kasutada topeltviitu (st viidad nii alla kui üles).
Efektiivsuse huvides peaks kuhja igal binomiaalpuul olema juures jär-
ku näitav lisaväli.
2
Binomiaalkuhjad
34
2.1
Operatsioonid
Operatsioonid
2
Binomiaalkuhjad
35
2.1
Operatsioonid
Ühendamisülesanne
Viia antud kahest binomiaalkuhjast ühe kõik kirjed teise.
– Sisend: kaks binomiaalkuhja.
2
Binomiaalkuhjad
36
2.1
Operatsioonid
Lahendusalgoritm
Algul ühendatakse binomiaalmetsad üheks metsaks järjestatud järjen-
dite põimimise  algoritmiga , käsitledes metsi järjenditena, kus kirjeteks
on neisse kuuluvad binomiaalpuud ja võtmeteks puude järgud.
Saadud mets käiakse läbi alustades vähimast järgust. . .
2
Binomiaalkuhjad
37
2.1
Operatsioonid
Lahendusalgoritmi jätk
– Kui  jooksva  puu järk on väiksem järgneva puu järgust, siis jät-
katakse sama tööd kohe järgmisest puust.
– Kui jooksva puu järk on võrdne nii järgmise kui ülejärgmise
omaga, siis samuti jätkatakse tööd kohe järgmisest puust.
– Kui jooksva puu järk on võrdne järgmisega, kuid väiksem üle-
järgmise omast, siis
∗ paigutatakse kahest võrdse järguga puust see, mille juure
kirje võti on suurem, ümber teise haruks,
∗ ja jätkatakse sama tööd edasi äsjatekkinud puust.
2
Binomiaalkuhjad
38
2.1
Operatsioonid
Lisamisülesanne
Lisada antud binomiaalkuhja antud kirje.
– Sisend: binomiaalkuhi, kirje.
2
Binomiaalkuhjad
39
2.1
Operatsioonid
Lahendusalgoritm
Luuakse binomiaalmets, mille ainus puu on 1-tipuline puu, mille ainsa
tipu kirje on antud kirje.
Ühendatakse antud binomiaalkuhi ja loodud uus 1-tipuline kuhi.
2
Binomiaalkuhjad
40
2.1
Operatsioonid
Otsimisülesanne
Otsida antud binomiaalkuhjast vähima võtmega kirje.
– Sisend: binomiaalkuhi.
– Väljund: vähima võtmega kirje positsioon.
2
Binomiaalkuhjad
41
2.1
Operatsioonid
Lahendusalgoritm
Käsitledes metsa järjendina, kus kirjeteks on sinna kuuluvad bino-
miaalpuud ja võtmeks puu juure kirje võti, rakendatakse järjestatud
järjendist vähima võtme otsimise algoritmi.
2
Binomiaalkuhjad
42
2.1
Operatsioonid
Eemaldamisülesanne
Eemaldada antud binomiaalkuhjast vähima võtmega kirje.
– Sisend: binomiaalkuhi.
– Väljund: vähima võtmega kirje.
2
Binomiaalkuhjad
43
2.1
Operatsioonid
Lahendusalgoritm
Kui kuhi on tühi, siis lõpetatakse ebaõnnestumisega.
Vastasel korral
– otsitakse üles puu, mille juure kirje võti on vähim;
– käsitledes metsa puude järjendina, tõmmata see puu vastava jär-
jendioperatsiooniga kuhjast välja;
– ühendatakse  eemaldatud  puu harude mets  eemaldamisel  järele
jäänud kuhjaga;
– tagastatakse eemaldatud puu juure kirje.
2
Binomiaalkuhjad
44
2.1
Operatsioonid
Keerukus
Kõik algoritmid on keerukusega O(log n), kus n on kuhja tippude arv
(ühendamise puhul kahe kuhja tippude koguarv).