7. Prioritetskøer (Heaps)

En heap er et komplett tre. Vi implementerer prioritetskøen som en binær heap, og kaller denne datastrukturen for enkelhets skyld bare heap. Som for andre binære trær har en heap to typer krav: strukturkrav og ordenskrav. Operasjoner på heapen kan ødelegge for disse kravene, så en slik opersjon må "rydde opp etter seg" før den terminerer.

Strukturkrav: En heap er et binært tre som er fullstednig fyllt (det er komplett), med mulig unntak av det nederste nivået, som fylles opp fra venstre til høyre.
Ordenskrav: Alle noder skal være mindre enn (eller lik, hvis vi godtar dupletter) sine barn. Unntak: rotnoden.

Fordi treet er komplett, kan det enkelt implementeres som et array (en tabell).

Implementer som en heap, får vi arbeidmengden O(log N) for innsetting og O(1) for sletting i en prioritetskø.

7.1 Innsetting

Innsetting i en heap er enkelt.
1) Lag et hull i den neste plassen i treet (sist i arrayet).
2) Hullet "bobles" oppover inntil mornoden har mindre verdi enn den noden vi skal sette inn. Og der setter vi noden inn.

7.2 Sletting av det minste elementet

I en priorietskø skal vi alltid bare slette det minste elementet.
1) Lag et hull i rot-noden (her ligger den minste verdien).
2) Finn frem det siste tallet i heapen (det er jo egentlig bare her vi har lov å slette i en heap).
3) Flytt hullet nedover ved å rykke opp det minste av barna.

7.3 Bruksområder

- Shortest-job-next
- Grådige algoritmer (Dijkstras algoritme - finner korteste vei)
- Sorteringsmaskin, se kodeeksempler:
heapsort.cpp
heaps2.cpp
Begge kodene er etter boka til Sedgewick.
 

7.4 Andre mulige implementasjoner

- Som lenkede lister (sortert / usortert)
- Som et vanlig binærtre
 

7.5 Kode

heap.h
heap.cpp