1
|
|
2
|
- Oppsummering av dagens forelesning:
- Motivasjon (prioriteskøer)
- Operasjoner
- Implementasjoner og
tidsforbruk
- Heap-implementasjonen<=
/li>
-  =
;
Strukturkravet
-  =
;
Heap-ordningskravet
-  =
;
Insert
-  =
;
DeleteMin
-  =
;
Tilleggsoperasjoner
-  =
;
Build Heap
- Anvendelser
-  =
;
Finn medianen og sortering
-  =
;
Hendelsessimulering (Event simulation)
- Binomialtrær-implementasjon
|
3
|
- Motivasjon
- I en vanlig kø (kapittel 3 i MAW) setter vi inn elementer i en
ende av
- køen og tar ut elementer i den andre enden (First In First Out
– FIFO).
- Ofte har vi bruk for å prioritere jobbene som vi legger i
køen: noe
- må gjøres med en gang, mens andre ting kan vente litt.<=
/li>
|
4
|
- Eksempel:
- Jobbfordeleren (scheduler) i operativsystemer
- En Unix-server har som oftest mange brukere tilkoblet samtidig, og=
li>
- hver bruker har mange jobber som kjører på en gang
(Netscape, Emacs,
- Java-kompilering, klokke, osv.).
- På en vanlig datamaskin i dag er det bare en prosessor (CPU),
så bare en
- jobb kan fysisk kjøre (utføres) på et gitt
tidspunkt.
- Det er helt uakseptabelt å la hver jobb kjøre ferdig
før neste jobb får
- slippe til.
|
5
|
- Løsning
- En mulig løsning er å plassere jobbene i en kø.<=
/li>
- Når=
en
jobb tas ut av køen, får den lov å kjøre en
liten stund (noen
- milliseku=
nder)
før den legges bakerst i køen igjen.
- På =
den
måten ser det ut som om alle jobbene kjører samtidig.=
li>
- Problemet er at korte jobber tar uforholdsmessig lang tid pga. all
ventingen.
- En god løsning er å senke prioriteten på jobber s=
om
allerede har kjørt
- lenge, slik at nye, korte jobber blir utført raskt.
|
6
|
- Operasjoner
- En prioritetskø må minst støtte følgende =
to
operasjoner:
- insert(x,p) som setter
element x inn i prioritetskøen med prioritet lik p
- (lite tall betyr høy prioritet, stort tall betyr liten prioti=
et).
- deleteMin som tar ut og
returnerer det elementet i køen som har høyest
- priortet (minst p).
- Vi skal senere se litt på noen andre operasjoner som en mer
avansert
- prioritetskø kan tenkes å støtte.
|
7
|
- Implementasjoner
- Det er flere opplagte måter å implementere en
prioritetskø på:
- Enkel pekerkjede
- setter alltid inn bakerst i pekerkjeden, O (1)
- må traversere listen for å finne det minste elementet, O=
(n)
|
8
|
- Sortert pekerkjede (A1 < A2 < < An)
- deleteMin tar alltid ut bakerst fra listen, O (1)
- ved innsetting må vi gå gjennom listen for å finne
riktig plass, O (n)
- Enkel pekerkjede er sannsynligvis bedre enn sortert pekerkjede fordi=
vi
- aldri kan ta ut flere elementer enn vi har satt inn.
- Søketrær
- I alle søketrær bruker både insert og deleteMin i
snitt O(log n) tid.
- Balanserte søketrær (f.eks. B-trær) bruker aldri =
mer
enn O (log n) tid,
- men slike trær er forholdsvis komplekse strukturer.
|
9
|
- Heap-implementasjonen
- En heap, også kalt binary heap, er et binært tre med et<=
/li>
- strukturkrav (hvordan treet ser ut) og et
- heap-ordningskrav (hvordan nodeverdiene er plassert i forhold til
hverandre).
- Heap-implementasjonen =
er
så populær at mange bruker ordet ‘heap’ som =
et
synonym for ‘prioritetskø’.
- Insert tar O (log n) t=
id i
verste tilfelle, men konstant tid i gjennomsnitt.
- DeleteMin tar O (log n)
både i verste tilfelle og i gjennomsnitt.
- Konstantleddene er
små!
|
10
|
- Strukturkravet til en heap
- En heap er et komplett binærtre, dvs. et tre hvor hvert niv&ar=
ing;
i treet er helt fylt
- opp med noder, med unntak av det nederste nivået som er fylt o=
pp
fra
- venstre mot høyre.
|
11
|
- Innsetting og sletting består i å la en verdi henholdsvis
flyte opp og synke
- ned i treet. Siden høyden er logaritmisk, vil operasjonene ik=
ke
bruke mer enn
- logaritmisk tid, dvs. O (log n).
- Vi skal tegne heaper som trær, men på grunn av
strukturkravet, behøver
- vi bare en enkelt array for å implementere en heap:
|
12
|
- Noden i posisjon H(i) har sitt venstre barn i H(2i), sitt høy=
re
barn i
- H(2i + 1) og forelderen i H(└i/2 ┘=
).
- Dermed blir operasjonene som traverserer treet ekstremt hurtige.
- Vi må bestemme en maksimal størrelse på heapen
på forhånd
- (evt. allokere mer plass når vi trenger det, men det er kostba=
rt).
|
13
|
- Ordningskravet til en heap:
- 1) Den minste verdien i treet er i roten.
- 2) Dette skal også gjelde for alle subtrær.
|
14
|
- Vi antar for enkelhets skyld at det bare er prioritetsverdiene som s=
kal
- lagres i heapen.
- Ordningskravet gjør at tilleggsoperasjonen findMin kan
- utføres i konstant tid.
- Hvis man ønsker en “max-heap”, kan man kreve at d=
et
største
- elementet skal være i roten av treet (og alle subtrær).<=
/li>
|
15
|
- Insert
- Vi må sikre oss at heap-kravene er oppfylt etter at innsetting=
en
er ferdig.
- Når vi skal sette inn et element X, må vi lage en
“boble” (tom node) i
- den neste ledige plassen, ellers vil ikke treet være komplett.=
- Vi sjekker om X kan settes inn der boblen står. Hvis det vil
ødelegge
- heap-ordningskravet, lar vi boblen flyte oppover i treet (percolate =
up)
- inntil den kommer til et sted hvor X kan settes inn.
|
16
|
- Eksempel:
- Sett inn et element med prioritet 8 i heapen på forrige siden.=
- 8 kan ikke settes inn i den nye boblen fordi forelderen i så f=
all
vil ha større
- verdi enn barnet (18 > 8). Vi lar derfor boblen bytte plass med 1=
8:
|
17
|
- Tidsforbruk:
- I verste fall må vi flytte boblen O (log n) ganger, men i
gjennomsnitt flyter
- boblen opp bare 1,607 nivåer, dvs. at innsetting tar konstant =
tid
i gjennomsnitt.
- Hvis elementet vi setter inn er den nye minsteverdien i heapen, vil<=
/li>
- boblen flyte helt opp til roten.
- For å slippe å teste på om vi er i roten (=/://3/3D plas=
s nr 1
i arrayen) hver
- gang vi flytter boblen, kan vi bruke en dørvakt (sentinel) i
posisjon 0 i arrayen.
- Dørvakten må ha en verdi som garantert er mindre enn al=
le
lovlige
- prioritetsverdier:
|
18
|
|
19
|
- DeleteMin
- Det er lett å finne det minste elementet, men når vi har
fjernet
- det, er det en tom boble i roten.
- Samtidig er vi nødt til å flytte den “siste”
noden X i heapen, siden treet
- skal krympe med et element og fortsatt være komplett.
- Hvis X kan plasseres i rotboblen uten å bryte ordningskravet, =
er
vi ferdig.
- I motsatt fall lar vi boblen synke nedover i treet (percolate down)<=
/li>
- inntil X kan settes inn i boblen.
- Når boblen skal synke nedover, lar vi den bytte plass med sitt
minste barn:
|
20
|
|
21
|
|
22
|
- Tidsforbruk:
- Det viser seg at i gjennomsnitt synker boblen nesten helt ned til
bladnoden,
- dvs. at deleteMin er O (log n) både i verste tilfelle og i
gjennomsnitt.
- Koding:
- Vi må passe på det spesialtilfellet at antall elementer i
heapen er like og
- boblen flyter ned til elementet med bare 1 barn.
|
23
|
|
24
|
- Andre heap-operasjoner
- Selv om findMin er lett, så er heap-ordningskravet ikke til hj=
elp
- hvis vi ønsker å implementere tilleggsfunksjonen findMa=
x.
- Det eneste vi vet om det største elementet, er at det befinner
seg i en
- bladnode (hvorfor vet vi det?)
- Siden cirka halvparten av nodene i et komplett binærtre er
bladnoder,
- er ikke det til noe særlig hjelp.
- Hvis det er viktig å vite hvor i heapen et gitt element er,
må vi
- bruke en annen datastruktur i tillegg, f.eks. en hash.
- Hvis kjenner heap-posisjonen, i, til et element, kan følgende
operasjoner
- utføres i O (log n) verstetid: DecreaseKey(i,Δ), Increas=
eKey(i,
Δ) og Delete(i).
|
25
|
- DecreaseKey(i, Δ)
- DecreaseKey minsker prioriteten til elementet i posisjon ’i=
217;
med verdien
- (H[i] =/://3/3D H[i]− =
Δ i
en heltalls-heap).
- Heap-ordningen kan bli ødelagt, så vi lar elementet flyte oppo=
ver i
- heapen inntil den er kommet til en “lovlig” plass.
- Eksampel (OS): En systemadministrator kan øke prioriteten til=
en
viktig jobb.
- IncreaseKey(i, Δ)
- IncreaseKey øker prioriteten til elementet i posisjon
’i’ med verdien
- (H[i] =/://3/3D H[i] + Δ=
;).
- Heap-ordningen kan bli ødelagt, så vi lar elementet syn=
ke
nedover i
- heapen inntil det er kommet på riktig plass.
- Eksampel (OS): Mange jobbfordelere senker automatisk prioriteten
på
- jobber som har kjørt lenge.
|
26
|
- Delete
- Delete fjerner elementet i posisjon ’i’ fra heapen. Det =
kan
gjøres ved
- først å utføre DecreaseKey(i,∞) og derette=
r DeleteMin.
- Eksampel(OS): Når en bruker dreper en prosess (kill), må=
den
fjernes fra
- prioritetskøen.
|
27
|
- BuildHeap
- Anta at du har N elementer som du ønsker å sette inn i =
en
tom heap.
- En enkel innsetting tar O (1) tid i gjennomsnitt og O (log n) tid i
verste fall.
- Dermed kan vi bygge heapen i O (n) gjennomsnittlig tid og O (n log n=
)
- verstetid ved å utføre Insert N ganger.
- Er det mulig å klare å få lineær tid ogs&ari=
ng;
i verste tilfelle?
- En smart BuildHeap-algoritme:
- 1. Sett de N elementene inn i et komplett binærtre, men uten
å tenke på om heap-ordingskravet er oppfylt.
- 2. for i=/://3/3D N div 2 downto 1
-
PercolateDown(i);
- PercolateDown(i) lar
elementet i posisjon ’i’ synke ned i treet.
|
28
|
|
29
|
|
30
|
- Vi ønsker å vise at algoritmen har verstetid O (n).
- Vi observerer at i eksemplet over er arbeidet (antall flyttinger/tes=
ter)
- proporsjonalt med antallet røde kanter.
- Antall røde kanter kan maksimalt være lik summen av
høydene til alle
- nodene i heapen.
- Hvis vi kan bevise at denne summen alltid er O (n), så er
algoritmen også O (n).
|
31
|
|
32
|
|
33
|
- Anvendelser
- Sortering
- Anta at vi skal sortere n elementer. Ved først å bru=
ke BuildHeap
og
- deretter deleteMin n ganger, har vi en rask O (n + n log n) =/://3/3D O (n=
log n)
- sorteringsalgoritme.
- Å finne medianen
- Vi kan også finne det k’te minste elementet ved å
bruke BuildHeap og
- deretter deleteMin k ganger. Vi har dermed en O (n log n)=
-algoritme
for å finne
- medianen (k =/://3/3D n=/://3/3D2).
|
34
|
- Hendelsesimulering
- Ved simulering (f.eks. av kassakøer i et supermarked) deler m=
an
tiden inn
- i diskrete biter kalt “ticks”.
- I stedet for for hvert tick å sjekke om det er registrert en
hendelse på dette
- tidspunktet, legger man hendelsene inn i en prioritetskø ordn=
et
etter
- hendelsestidspunktet.
- Neste hendelse kan da taes ut fra toppen av heapen.
- Dette sparer mye prosesseringstid, spesielt ved høy
tidsoppløselighet.
|
35
|
- Binomialtrær-implementasjon (Binomial Queues)
|
36
|
- Den store fordelen av binomial queues er et det er veldig lett &arin=
g;
sette dem sammen (merge).
|
37
|
- Hvis vi skal representere et binomial queue med 6 noder og en med 7<=
/li>
- for eksampel, tar vi utgangspunkt i binær representasjoner av =
6 og
7.
- 13=/://3/3D1102 o=
g 7=/://3/3D1112. Vi
representerer den første køen ved B2 og B
0
- og den andre ved B2, B1 og B0.
|
38
|
|
39
|
|
40
|
- Neste gang:
- Innledning i grafer
- Topologisk sortering
- Korteste vei
|