4.4 Heap og prioritetskø

En samling der du kan legge inn elementer og alltid hente ut det med høyest
prioritet — i en min-prioritetskø betyr det det minste elementet.

Kontrakten er tre operasjoner: Insert (legg inn), RemoveMin (fjern og
returner det minste) og FindMin (les det minste). Med en min-heap koster de
$O(\log n)$, $O(\log n)$ og $O(1)$. Prioritetskøen er ikke en datastruktur i seg
selv, men en kontrakt som kan oppfylles på flere måter — se
kap. 1.4 om at et balansert søketre gir samme orden.

I en min-heap er hver forelder mindre enn eller lik begge barna sine.

Ordningen går opp og ned, aldri sideveis: det står ingenting om forholdet
mellom to søsken, og ingenting om forholdet mellom to noder på samme nivå.
Venstre barn kan godt være større enn høyre barn.

Konsekvensen er at det minste elementet garantert ligger på rota — og bare
det. Resten av strukturen er så godt som usortert.

En heap er alltid et komplett binært tre: alle nivåer er helt fylt, bortsett
fra det nederste, som fylles fra venstre.

Dette er ikke pynt. Det er strukturkravet som gjør at treet kan lagres som ett
array uten hull, og som holder høyden på $\lfloor \log_2 n \rfloor$ uansett
hvilke verdier som legges inn. En heap kan aldri bli skjev slik et vanlig
søketre kan.

$$\text{forelder}(i) = \lfloor (i-1)/2 \rfloor, \qquad \text{barn}(i) = 2i+1 \ \text{og} \ 2i+2$$

Fordi treet er komplett, er det ingen hull i arrayet, og hver indeks kan regnes
om til forelder og barn med ren aritmetikk. IN2010 indekserer fra 0, og
formlene over er de eneste som gjelder i denne boka. Framstillinger som lar rota
ligge på indeks 1, bruker andre formler, og de gir feil node her.

Elementet på indeks $i$ har venstre barn på $2i+1$ og høyre barn på $2i+2$ — men
bare hvis indeksene finnes.

Med $n$ elementer i heapen gjelder:

- $2i+1 \ge n$: noden er et blad og har ingen barn.
- $2i+1 < n$ men $2i+2 \ge n$: noden har bare venstre barn.
- ellers: noden har begge barna.

Disse tre tilfellene er hele innholdet i felle #3 — down-heap som ikke
sjekker at barnet finnes.

Reparasjonen etter en innsetting: det nye elementet sammenlignes med forelderen
sin og bytter oppover så lenge det er mindre.

Én sti fra bunnen mot rota, høyst $\lfloor \log_2 n \rfloor$ bytter, altså
$O(\log n)$. Ingen andre deler av heapen berøres. Stopper når forelderen er
mindre enn eller lik elementet, eller når rota er nådd.

Reparasjonen nedover: elementet sammenlignes med det minste av barna sine og
synker så lenge det er størst.

Én sti fra rota mot bunnen, høyst $\lfloor \log_2 n \rfloor$ bytter, altså
$O(\log n)$. To sjekker er obligatoriske: at venstre barn finnes
($2i+1 < n$), og at høyre barn finnes ($2i+2 < n$) før det sammenlignes.
Å utelate dem er felle #3.

Legger elementet på første ledige indeks, altså bakerst i arrayet, og lar det
stige med sift-up.

$O(\log n)$ i verste tilfelle, der $n$ er antall elementer. Beste tilfelle er
$O(1)$ — når elementet allerede er større enn forelderen sin der det landet.
Strukturkravet gjør at det ikke finnes noen annen plass å legge det.

Returnerer H[0], flytter det siste elementet til rota, krymper arrayet og
kjører down-heap fra indeks 0.

$O(\log n)$, der $n$ er antall elementer. Selve uthentingen er $O(1)$; det er
reparasjonen som koster. Merk at det er det siste elementet som flyttes opp,
ikke et av barna — alt annet ville brutt strukturkravet.

Leser det minste elementet uten å fjerne det. Det ligger alltid på indeks 0.

$O(1)$. Dette er heapens billigste operasjon og hele grunnen til at strukturen
brukes som prioritetskø. Kontrast: å finne det største i en min-heap er
$O(n)$.

Gjør et vilkårlig array om til en heap ved å kjøre down-heap fra indeks
$\lfloor n/2 \rfloor - 1$ og bakover til 0.

$O(n)$ — ikke $O(n \log n)$. Grunnen er arbeidsfordelingen: halvparten av
nodene er blader og gjør ingenting, en firedel synker høyst ett nivå, en åttedel
høyst to. Summen holder seg under $2n$. Påstanden «å bygge en heap fra et
vilkårlig array tar $O(n \log n)$» er en fast distraktor, og den er usann.

De to sjekkene som må stå i enhver down-heap: 2*i + 1 < n for om venstre barn
finnes i det hele tatt, og 2*i + 2 < n før høyre barn brukes i en
sammenligning.

Uten dem leser algoritmen utenfor arrayet. Dette er felle #3 i bokas
feilregister, og den eneste fellen i Del 4 med eksplisitt takpoeng: mangler
sjekken, er full uttelling utelukket uansett hvor riktig resten er.

Når et element skal synke, byttes det med det minste av de to barna — ikke
med venstre barn, og ikke med det største.

Grunnen: bytter du med det største, blir det du flyttet opp større enn søskenet
sitt, og du har laget et nytt brudd rett under deg. Med det minste blir den nye
forelderen mindre enn begge barna, og bruddet forsvinner.

Det største elementet i en min-heap ligger i et blad, men heap-egenskapen
sier ikke hvilket. Bladene er omtrent halvparten av nodene, og alle må sjekkes.

Kjøretiden er derfor $O(n)$, ikke $O(\log n)$. Påstanden «du kan finne det
største elementet i en min-heap i $O(\log n)$» er usann og er en fast
distraktor på Del 1. Trenger du både min og max billig, trenger du to strukturer
— eller en annen struktur.

Å snu arrayet til en min-heap gir ikke en gyldig max-heap.

Reverseringen snur rekkefølgen i arrayet, men den snur ikke forelder–barn-
forholdene: forelderen til indeks $i$ blir ikke barnet til den reverserte
indeksen. Konkret gir min-heapen 5, 8, 6, 9, 12, 7, 10 reversert
10, 7, 12, 9, 6, 8, 5, der rota 10 har barnet 12 — brudd med én gang. Vil du ha
en max-heap, må du bygge den med motsatt sammenligning.

I et komplett binært tre ligger over halvparten av nodene på de to nederste
nivåene.

Antall noder dobles for hvert nivå nedover, så det nederste nivået alene rommer
omtrent halvparten. Konkret, for $n = 15$: nivåene med indeks 3 til 6 (4 noder) og
7 til 14 (8 noder) utgjør 12 av 15 noder, altså 80 %. Denne fordelingen er hele
grunnen til at BuildHeap er $O(n)$.

Fordi treet alltid er komplett, er dette den lavest mulige høyden for $n$ noder —
en heap kan aldri bli skjev slik et vanlig søketre kan. Det er derfor Insert og
RemoveMin er $O(\log n)$ også i verste tilfelle. Merk skillet: en heap med 8
elementer har høyde 3 og fire nivåer.

Speilbildet av min-heapen: hver forelder er større enn eller lik begge barna,
og det største elementet ligger på rota.

Samme struktur, samme indeksformler, samme kjøretider — bare motsatt
sammenligning i sift-up og down-heap. En max-heap fås ved å bygge på nytt med
snudd sammenligning, ikke ved å reversere arrayet til en min-heap.

Bygger en heap av arrayet ($O(n)$) og henter deretter ut elementene ett for ett
($n$ ganger $O(\log n)$).

Totalt $O(n \log n)$ i alle tilfeller, in-place, men ikke stabil —
uthentingen flytter elementer over lang avstand. Merk hvor de to tallene kommer
fra: byggingen er lineær, uthentingen er logaritmisk per element. Se
kap. 2.2.

Delvis riktig array gir delvis uttelling, så lever alltid noe. Tegner du treet i
tillegg, er det greit — men arrayet må stå der, for det er det sensor ber om.

Begge gir $O(\log n)$ på innsetting og uthenting av det minste elementet, så i
$O$-klasse er de like — påstanden om at et AVL-tre kan brukes som prioritetskø
med samme orden som en heap, er sann.

Heapen vinner likevel i praksis: den er ett array uten pekere, den har lave
konstantfaktorer, og den bygges på $O(n)$. Søketreet vinner når du i tillegg
trenger sortert traversering eller søk på vilkårlige nøkler. Se
kap. 4.3.

Heapen ordner opp–ned: forelderen er mindre enn eller lik begge barna. Et
binært søketre ordner venstre–høyre: alt til venstre er mindre, alt til høyre
er større.

Å blande dem er felle #9 i bokas feilregister. To følger å merke seg: i en
min-heap kan venstre barn godt være større enn høyre barn, og arrayet til en heap
er ikke sortert. Se kap. 4.1.

Del 1-sjangeren der du får en struktur og en operasjonsrekke og skal oppgi kun
sluttilstanden.

Minst én per sett, ofte to, og heapen er den hyppigste kandidaten (86 %, 6 av 7
sett). Formatet er strengt: hele arrayet, indeks fra 0. Delvis riktig tilstand
gir delvis uttelling, så la aldri svaret stå tomt.

Del 1-sjangeren med sant/usant-påstander som rettes automatisk, med
antigjettings-skalering: summen skaleres slik at ren gjetting i snitt gir
null poeng.

Heap-faktaene er blant de mest brukte: BuildHeap er $O(n)$, max i en min-heap
er $O(n)$, reversering gir ikke en max-heap, venstre barn er ikke alltid minst.
Merk den andre halvdelen av regelen: på vanlige korte svar, som ikke er
strafferammet, teller ubesvart som feil, så der skal du alltid svare.