Redigerer Tre (datastruktur) (avsnitt)

==Binærheaper==

En binærheap er en form for [[prioritetskø]] som representeres ved hjelp av et tre. I motsetning til andre typer trær implementeres vanligvis ikke en binærheap ved hjelp av grafer, men med bruk av et [[array]].

En binærheap er et binærtre som er fullstendig fylt opp, med et mulig unntak for det nederste nivået, som fylles opp fra venstre mot høyre. En binærheap med høyde <math>h</math> vil derfor inneholde mellom <math>2^h</math> og <math>2^{h+1}-1</math> noder. Dette gjør at at operasjoner på en binærheap vil være <math>O(logN)</math>.

Ved hjelp av denne datastrukturen er det lett å finne det minste elementet i en datamengde (eventuelt det største, om man velger å heller implementere treet slik). Dette kommer av at det minste elementet i en binærheap alltid ligger i roten. Siden hvert subtre også er en binærheap, vil hver node ha mindre verdi enn alle deres barn, barnebarn og andre «etterkommere».

Disse attributtene gjør også at det er greit å sette nye elementer inn i en binærheap. En sett inn-operasjon vil være <math>O(1)</math> gjennomsnittlig, og <math>O(logN)</math> i verste fall. Dette fører også med seg at oppbygningen av en binærheap vil i gjennomsnitt være en <math>O(N)</math>-operasjon.
{{Autoritetsdata}}

[[Kategori:Trær (datastrukturer)| ]]

[[de:Datenstruktur#Baum]]