Heap

Heap (norsk haug) er en datastruktur brukt i informatikk, mye brukt til å lage prioritetskø og for å sortere data.

En haug lagrer data i et s.k. tre.  Ethvert element E er koblet til «barn», som skal ha en verdi lik eller mindre enn E.  Dette sikrer at roten i treet vil være det største i datamengden, og at leting etter høyeste verdi tar O(1) tid. Leting etter vilkårlig verdi blant de N som ligger i haugen, tar derimot O(N) tid, da det ikke er klart hvor i haugen nye element legges. En haug kan også brukes til det motsatte, der hvert element E peker til barn som er høyere enn seg E.  Altså vil roten da være det minste i mengden. De fleste programmeringsspråk har ferdige hjelpemidler for å ta i bruk haug.

 Arbeidstid 
Ved uttak og innsetting må en umiddelbart omordne treet slik at alle element har barn mindre enn seg. Ved uttak byttes rotnode (den minste) ut med det sist innlagte elementet SIST, hvorpå SIST skiftes nedover inntil det når et nivå der begge barn er mindre enn SIST.  Dette tar O(log N) tid.  Ved innsetting av element NY, plasseres dette på laveste nivå og skiftes oppover i treet inntil det har nådde et nivå der begge barn er mindre enn NY. Dette tar O(log N) tid i verste fall, men vil over tid skje på O(1) tid.

Hvis et element skal endre verdi (ned eller opp), vil det også måtte skifte (opp eller ned) nivå. Sletting av et element ordnes ved å sette verdien til det minst mulige, slik at det skiftes til lavest mulige nivå og da tas ut på O(1) tid.  Fletting av to hauger tar O(N) tid.

 Varianter 
En k-haug er en heap der hvert element har k barn, hvilket vil gi færre nivå og derved raskere uttak og innsetting.  Det vanligste er 2-hauger (binære) som vist i figuren, da disse kan lages med tabell (datastruktur) og aritmetikk basert på bitskifting.  Disse gir balanserte trær, der omtrent halvparten er løvnoder på laveste nivå og 3/4 på nest laveste nivå, slik at innsetting kan gjøres på O(1) amortisert (gjennomsnittlig) tid.

Hvis rask fletting er ønskelig brukes en venstreorientert haug (leftist).  Dette er en 2-haug som tilstreber ubalanse ved å alltid sikre en «tyngre» venstre- enn høyreside. Fletting gjøres da raskest mot rotens kortere høyreside, og da på O(log N) tid, med den ulempe at innsetting tar O(log N) tid.

Kategori:Datastrukturer