Hauger og binære søketrær

Et tre du kan lagre i et array

Tenk deg en turnering der vinneren av hver kamp går videre, og den aller beste til slutt står øverst. En haug er bygd på samme idé: et tre der den som dominerer alltid ligger over dem den slår. Mer presist er en haug et nesten komplett binærtre — alle nivåer er fulle bortsett fra kanskje det nederste, som fylles fra venstre. I en maks-haug er hver forelder minst like stor som barna sine, så det største elementet havner i rota.

Det fine er at vi ikke trenger pekere for å lagre dette treet. Fordi treet er nesten komplett, kan vi legge nodene rett etter hverandre i et array, nivå for nivå, fra venstre mot høyre. Da finner vi forelder og barn med ren regning på indeksen, slik ƒhaug-indeksering (1-basert) viser: barna til node $i$ ligger på $2i$ og $2i+1$, og forelderen på $\lfloor i/2\rfloor$ (her teller vi fra 1). Ingen ekstra minne til pekere, og hopp opp og ned i treet blir enkle multiplikasjoner.

Maks-haug-egenskapen sier altså at $A[\lfloor i/2\rfloor ]\ge A[i]$ for hver node $i$ som ikke er rota — se ƒmaks-haug-egenskapen. Legg merke til hva den ikke sier: et venstre barn kan godt være mindre enn et barnebarn på en annen gren. En haug er ikke et sortert array. Den gir bare én garanti — at toppen er størst — og det er akkurat nok til å bygge en rask prioritetskø.

Max-Heapify: la et for lite element synke

Anta at venstre og høyre delre allerede er gyldige maks-hauger, men at roten i et lite delre er for liten — den bryter egenskapen mot ett av barna. heapify (max-heapify) retter dette ved å la det for lille elementet synke nedover, ett steg om gangen, til det havner på riktig plass.

Max-Heapify(A, i, n):           # n = antall elementer i haugen
    størst = i
    v = 2*i                     # venstre barn (1-basert)
    h = 2*i + 1                 # høyre barn
    hvis v <= n og A[v] > A[størst]:
        størst = v
    hvis h <= n og A[h] > A[størst]:
        størst = h
    hvis størst != i:
        bytt A[i] og A[størst]
        Max-Heapify(A, størst, n)

Vi sammenligner forelderen med begge barna, finner den største av de tre, og bytter forelderen ned dit hvis den ikke allerede er størst. Etter byttet kan vi ha ødelagt egenskapen lenger ned, så vi kaller Max-Heapify på nytt der elementet havnet. Sporet følger én vei fra noden og ned mot et blad. Siden et nesten komplett binærtre med $n$ noder har høyde $h=\lfloor \lg n\rfloor$ — se ƒhøyde av en haug — koster ett kall $O(\lg n)$. Det er kjerneoperasjonen alt annet i kapittelet bygger på.

Build-Max-Heap: bygg haugen nedenfra

Hvordan gjør vi et helt uordnet array om til en maks-haug? Det naive svaret er å sette inn elementene ett for ett, men det er ikke det smarteste. build-max-heap gjør det motsatt: den starter nederst og jobber oppover.

Bladene er allerede gyldige hauger i seg selv — et enslig element bryter ingen regel. Så vi trenger bare å kjøre Max-Heapify på de indre nodene, og vi tar dem i synkende rekkefølge fra den siste forelderen og opp til rota:

Build-Max-Heap(A, n):
    for i fra floor(n/2) ned til 1:
        Max-Heapify(A, i, n)

Et raskt overslag sier $n$ kall à $O(\lg n)$, altså $O(n\lg n)$. Men det er for pessimistisk, og ƒbuild-max-heap forteller hvorfor: arbeidet er faktisk $O(n)$. Nøkkelen er at de aller fleste nodene ligger nær bunnen og har kort vei å synke. Bare halvparten av nodene er blader (null arbeid), en fjerdedel ligger ett nivå opp (høyst ett steg), og så videre. Summen av alt synke-arbeidet konvergerer til en konstant ganger $n$. Dette er en viktig forskjell fra $n$ gjentatte innsettinger, som virkelig koster $\Theta (n\lg n)$.

Heapsort: sortér på stedet

Med Build-Max-Heap på plass faller en sorteringsalgoritme nesten ut av seg selv. heapsort bygger først en maks-haug, og utnytter så den ene garantien vi har: det største elementet ligger i rota.

Heapsort(A, n):
    Build-Max-Heap(A, n)
    for i fra n ned til 2:
        bytt A[1] og A[i]          # størst flyttes bakerst
        n = n - 1                  # krymp haugen med ett
        Max-Heapify(A, 1, n)       # gjenopprett haugen

Vi bytter rota (det største) med det siste elementet i haugen. Da er det største på sin endelige plass bakerst. Vi krymper haugen med ett, slik at det nettopp plasserte elementet er trygt utenfor, og kjører Max-Heapify på den nye rota for å gjenopprette egenskapen. Gjenta til bare ett element står igjen. Hvert av de $n$ stegene koster $O(\lg n)$, så Heapsort kjører i $\Theta (n\lg n)$ — se ƒheapsort — og det på stedet, uten ekstra array slik Mergesort krever.

Prioritetskø: haugen som verktøy

En haug er mer enn en sorteringstriks. Den er den naturlige implementasjonen av en prioritetskø — en abstrakt datatype som alltid leverer det elementet med høyest prioritet, uansett innsettingsrekkefølge. Tenk på et sykehus der den mest kritiske pasienten alltid skal behandles først, eller en skedulerer som plukker jobben med høyest hastegrad.

To operasjoner bærer det meste. Hent-maks leser rota i konstant tid; for å fjerne den flytter vi det siste elementet opp til rota og kjører Max-Heapify, i $O(\lg n)$. Sett-inn legger det nye elementet bakerst og lar det stige oppover så lenge det er større enn forelderen, også $O(\lg n)$. Begge de dyre operasjonene følger én sti i et tre av logaritmisk høyde, og det er nettopp derfor haugen vinner: en usortert liste gir rask innsetting men treg uthenting, en sortert liste det motsatte — haugen balanserer begge på $O(\lg n)$.

Binære søketrær: hold alt sortert

Hauger er gode på «gi meg den største», men dårlige på «ligger 42 her?» eller «hva er nest minst?». For slike spørsmål bruker vi et binært søketre (bst). Et binært søketre ordner nøklene etter en strengere regel enn haugen: for hver node er alle nøkler i venstre delre mindre, og alle i høyre delre større, enn noden selv.

Den regelen gjør søk enkelt. Vil du finne en nøkkel, starter du i rota og sammenligner: er nøkkelen mindre, gå til venstre; er den større, gå til høyre; er den lik, har du funnet den. Du følger én sti nedover og forkaster et helt delre ved hvert steg — samme idé som binærsøk, men i en trestruktur som tåler innsetting og sletting underveis.

BST-Søk(node, nøkkel):
    mens node != null og nøkkel != node.nøkkel:
        hvis nøkkel < node.nøkkel:
            node = node.venstre
        ellers:
            node = node.høyre
    returner node

Innsetting følger samme sti til den faller ut av treet, og henger den nye noden på som et blad der søket endte. Alle disse operasjonene koster $O(h)$ der $h$ er treets høyde — se ƒbst-operasjoner. Det er den store haken: høyden avhenger av formen. Et balansert tre har $h=O(\lg n)$ og er kjapt, men setter du inn allerede sorterte nøkler, vokser treet til en lang kjede med $h=n$, og søk blir like tregt som i en liste. Selvbalanserende varianter retter dette, men er utenfor pensum her.

Sletting og inorden-traversering

Sletting er den trådigste operasjonen, fordi vi må fjerne en node uten å bryte ordningen. Tre tilfeller: en node uten barn klippes bort direkte; en node med ett barn erstattes av det barnet; en node med to barn er vanskeligst. Da finner vi nodens etterfølger — den minste nøkkelen som er større, altså neste node i sortert rekkefølge — kopierer dens nøkkel inn, og sletter etterfølgeren i stedet (den har høyst ett barn, så vi er tilbake i et enkelt tilfelle).

Til slutt en vakker egenskap. Besøker du nodene i inorden-traversering-rekkefølge — først hele venstre delre, så noden selv, så hele høyre delre — får du nøklene i stigende orden, slik ƒinorden-traversering av bst viser. Et BST er på sett og vis et array sortert «på langs»: traverser det inorden, og du leser ut en ferdig sortert liste i $\Theta (n)$. Der haugen gir deg den største raskt, gir søketreet deg hele ordningen og raskt oppslag på enhver nøkkel.