3.1 Hauger og Heapsort

I en maks-haug er hver forelder større enn eller lik begge barna sine.

Ordningen går opp og ned, aldri sideveis. Det står ingenting om forholdet
mellom to søsken: venstre barn kan godt være større enn høyre barn, og to
noder på samme nivå kan stå i hvilken som helst rekkefølge.

Konsekvensen er at det største elementet garantert ligger på rota — og
bare det. Resten av arrayet er så godt som usortert, og det er meningen: en
haug er billig nettopp fordi den lover lite.

Formelt, for hver indeks $i$ som har barn: $A[\lfloor i/2\rfloor] \ge A[i]$.

En maks-haug lagres som et helt vanlig array A[1..n], fylt nivå for nivå
ovenfra og ned, og venstre før høyre innenfor hvert nivå. Rota ligger på
A[1].

Denne boka indekserer fra 1, slik CLRS gjør, og slik oppgavene og
løsningsforslagene i TDT4120 gjør. Det er ikke en smakssak: hele
indeksregningen under henger på det, og en formel fra en annen
indekseringsvane gir feil node hver eneste gang.

Fordi treet alltid fylles nivå for nivå uten hull, er høyden $\lfloor \lg n \rfloor$ — den lavest mulige for $n$ noder. Alt som koster «én sti opp eller
ned» er derfor $O(\lg n)$.

Fra en indeks $i$ finner du hele familien med tre regnestykker, uten å tegne
noe:

forelderen ligger på $\lfloor i/2\rfloor$, venstre barn på $2i$ og høyre barn
på $2i+1$.

Kanttilfellene er der oppgaver felles. Indeks 1 er rota og har ingen
forelder. Er $2i > n$, har noden ingen barn i det hele tatt — den er et blad.
Er $2i \le n$ men $2i+1 > n$, har den bare venstre barn, og da skal du bare
sammenligne med det ene.

Alle tre regnestykkene er $\Theta(1)$: konstant tid, uansett hvor stor haugen
er.

Skillet finnes fordi to av operasjonene krymper haugen uten å krympe arrayet:
Heap-Extract-Max flytter siste haugelement til rota og setter A.heap-size
ned med én, og Heapsort legger det største elementet bakerst i arrayet og
tar det ut av haugen ved å gjøre det samme.

Praktisk konsekvens for håndkjøring: elementene bak A.heap-size ligger
fortsatt i arrayet, men de er usynlige for Max-Heapify. Oppgaven ber
som regel om hele arrayet, og da skal de med — men de skal ikke sammenlignes.

reparerer ett brudd på haugegenskapen ved å la elementet på indeks $i$ sive
nedover mot det største barnet så lenge et barn er større.

Kjøretid $O(\lg n)$ — én sti fra $i$ og ned, aldri forgrening.

Krever at begge deltrærne under $i$ allerede er gyldige maks-hauger. Er
den betingelsen brutt, reparerer rutinen ikke hele treet.

gjør et vilkårlig array om til en maks-haug på stedet ved å kalle
Max-Heapify for hver indeks fra $\lfloor n/2\rfloor$ og nedover til 1.

Kjøretid $\Theta(n)$ — ikke $\Theta(n\lg n)$. Den løse tellingen «$n/2$
kall à $O(\lg n)$» er en gyldig øvre grense, men ikke stram: halvparten av
nodene er blader med null arbeid.

Retningen er et krav. Løkka må telle nedover, ellers er Max-Heapifys
prebetingelse brutt.

fjerner og returnerer det største elementet: leser A[1], flytter det siste
haugelementet dit, reduserer A.heap-size med én og kaller Max-Heapify(A, 1).

Kjøretid $O(\lg n)$ — alt bortsett fra reparasjonen er konstant arbeid.

Krever A.heap-size $\ge 1$. Og merk: rutinen kontrollerer ikke at rota
faktisk er maksimum. Er inputen ikke en gyldig haug, returnerer den likevel
A[1].

leser det største elementet uten å fjerne det.

Kjøretid $\Theta(1)$, fordi maksimum per definisjon ligger på A[1] i en
gyldig maks-haug.

Det er denne operasjonen som gjør haugen til en prioritetskø: «hva er det
viktigste akkurat nå?» besvares uten å lete.

setter inn et nytt element ved å legge det bakerst i haugen og la det stige
oppover mot rota så lenge forelderen er mindre.

Kjøretid $O(\lg n)$ — én sti fra bladet og opp.

Retningen er motsatt av Max-Heapify: her siles det oppover, og
sammenligningen går bare mot forelderen, ikke mot søsken.

sorterer stigende ved å bygge en maks-haug og deretter bytte A[1] med
siste haugelement, krympe haugen og reparere rota — $n-1$ ganger.

Kjøretid $\Theta(n\lg n)$ i alle tilfeller. På stedet, og ustabil.

At grensen er tett og ikke bare øvre, kommer av at ingen input gjør
Heapsort raskere: den bygger og tømmer haugen likt uansett.

kravet som gjør et array til en maks-haug: hver forelder er større enn eller
lik begge barna sine, altså $A[\lfloor i/2\rfloor] \ge A[i]$ for alle $i \ge 2$.

Ordningen er opp–ned. Det finnes ingen venstre–høyre-orden: to søsken
kan stå i hvilken som helst rekkefølge.

Konsekvensen er at bare maksimum har en garantert plass. Resten av arrayet er
tilnærmet usortert.

haugen lagres som et vanlig array, fylt nivå for nivå ovenfra og ned og
venstre før høyre. Rota ligger på A[1].

Kostnaden for å finne familien til en node er $\Theta(1)$: ingen pekere, bare
regning.

Indeks fra 1 er konvensjonen i denne boka, og den som brukes i TDT4120s
oppgaver og løsningsforslag.

tre regnestykker som erstatter pekere: forelderen ligger på $\lfloor i/2\rfloor$, venstre barn på $2i$ og høyre barn på $2i+1$.

Alle tre er $\Theta(1)$.

Kanttilfellene: indeks 1 har ingen forelder. Er $2i > n$, er noden et
blad. Er $2i \le n$ men $2i+1 > n$, har noden bare venstre barn.

antall elementer som teller som en del av haugen akkurat nå — ikke det samme
som arrayets lengde.

Skillet koster ingenting å vedlikeholde ($\Theta(1)$ per endring), men det er
avgjørende ved håndkjøring.

Heap-Extract-Max og Heapsort krymper haugen uten å krympe arrayet.
Elementene bak A.heap-size ligger fortsatt der, men er usynlige for
Max-Heapify.

antall kanter fra rota ned til det dypeste bladet.

For en haug med $n$ elementer er høyden $\lfloor \lg n\rfloor$, altså
$\Theta(\lg n)$.

Grunnen er at treet alltid fylles nivå for nivå uten hull. Det er denne
høyden som gjør Max-Heapify, Heap-Extract-Max og Max-Heap-Insert til
$O(\lg n)$-operasjoner.

en datastruktur som støtter «gi meg det viktigste elementet» og «legg til et
nytt element», uten å holde alt sortert.

Med en maks-haug koster oppslaget $\Theta(1)$ og de to endringene $O(\lg n)$
hver.

Du møter den igjen som motor i Dijkstra og MST-Prim i Del 4, der
spørsmålet «hvilken node er nærmest nå?» stilles om og om igjen.

en algoritme er på stedet når den omorganiserer inputarrayet direkte og bare
bruker et konstant antall hjelpevariabler ved siden av.

Ekstra plassbruk: $\Theta(1)$.

Heapsort og Build-Max-Heap er på stedet. Merge-Sort er det ikke — den
trenger et hjelpearray på $\Theta(n)$ celler.

en sortering er stabil når to elementer med lik nøkkel beholder den
innbyrdes rekkefølgen de hadde i inputen.

Heapsort er ustabil. Motbevis: 3a, 3b, 1c sorteres til 1c, 3b, 3a,
mens en stabil sortering ville gitt 1c, 3a, 3b.

Grunnen er at byttene flytter elementer over lange avstander i arrayet — i
første runde hopper rota helt bakerst, forbi alt som ligger imellom.

regelen som styrer hvilken vei Max-Heapify går: elementet bytter med det
største av de to barna, ikke med venstre barn og ikke med det minste.

Det koster én ekstra sammenligning per nivå, altså fortsatt $O(\lg n)$.

Bytter du med det minste barnet, står du igjen med et nytt brudd rett under
deg — feilen er flyttet, ikke rettet.

alle indekser $i > \lfloor n/2\rfloor$ har $2i > n$ og dermed ingen barn. En
node uten barn er allerede en gyldig maks-haug med ett element.

Å hoppe over dem sparer omtrent halvparten av kallene, men endrer ikke
kjøretiden: den er $\Theta(n)$ uansett.

Det er derimot en fast kilde til feil i håndkjøring å starte på $n$ eller på
1 i stedet.

nodene uten barn, altså alle indekser $i$ med $2i > n$. De utgjør omtrent
halvparten av haugen.

Antallet er $\lceil n/2 \rceil$.

De er nøkkelen til $\Theta(n)$-analysen: halvparten av nodene gjør null
arbeid under Build-Max-Heap, og en firedel gjør høyst ett bytte.

to strukturer som forveksles systematisk, og som ordner i hver sin retning.

Begge har $\Theta(\lg n)$ som naturlig arbeidsmengde per operasjon, men de
svarer på ulike spørsmål.

Maks-haugen ordner opp–ned (forelder $\ge$ begge barn) og gir deg
maksimum i $\Theta(1)$. Søketreet ordner venstre–høyre og lar deg søke
etter en bestemt nøkkel. En haug kan ikke søke effektivt; et søketre kan ikke
love deg maksimum uten å gå til høyre spiss.

når en oppgave ber deg utføre en haugoperasjon, følger du pseudokoden linje
for linje — også når inputen ikke er en gyldig maks-haug.

Kostnaden er den samme som ellers; det er svaret som blir et annet.

Reparerer du først, svarer du på et annet spørsmål enn det som ble stilt.
Dette er felle #10 i bokas feilregister.

svaret på en haugoppgave er hele arrayet, kommaseparert, med indeks fra
1 — og A.heap-size når haugen er krympet.

Det tar ett sekund å skrive og gir full uttelling.

Et pent tegnet tre uten arrayet under gjør det ikke, og heller ikke «bare de
elementene som ble flyttet».

oppgavetypen der du utfører en navngitt algoritme steg for steg på papir og
oppgir sluttilstanden.

Den er den hyppigste håndkjøringssjangeren i faget, og hauger og søketrær er
de to vanligste strukturene: temaet er registrert i 16 av de 17 settene i
grunnlaget.

Svarformen er kun sluttilstanden, i det formatet oppgaven ber om. En
forklaring av hvordan algoritmen virker, gir ingen ekstra uttelling.

oppgavetypen der du oppgir kjøretiden til en navngitt operasjon.

Svarformen er ett uttrykk, i det strammeste som er riktig — og med $\Theta$
der grensen er tett og $O$ der bare øvre grense er vist.

Her ligger felle #9: å skrive $\Theta(n\lg n)$ for Build-Max-Heap, som er
$\Theta(n)$.