Innholdsfortegnelse:
Definisjon - Hva betyr Heap?
En haug, i sammenheng med datastrukturen, er en trebasert datastruktur som tilfredsstiller bunkeegenskapen, der hvert element tildeles en nøkkelverdi eller vekting. Den lavere verdien nøkkelen har alltid en overordnet node med en høyere verdi nøkkel. Dette kalles en max-heap-struktur, og blant alle noder har rotnoden den høyeste nøkkelen.
Noen ganger har en trebasert struktur en omvendt strukturregel, der et element med en nøkkel med høyere verdi alltid har en lavere verdi som en overordnet node. Dette kalles en min-haugestruktur, og blant alle nodene har rotnoden den laveste nøkkelen.
Techopedia forklarer Heap
Det er ingen praktiske begrensninger for antall barn hver node kan ha i en haug, selv om hver node vanligvis har to, på det meste. Heapen regnes som den mest effektive implementeringen av en abstrakt datatype, kjent som prioriteringskøen. Heapimplementering er viktig i forskjellige grafalgoritmer (inkludert Dijkstra's algoritme) så vel som i heapsortsorteringsalgoritmen.
Heaps har flere varianter som fungerer som abstrakte datatypeprioriteringskø-implementeringer med høy effektivitet. Mange applikasjoner, for eksempel grafalgoritmer, krever implementering av prioriterte køer.
En matrise er den vanligste implementeringsformen for heap, der det ikke er behov for noen pekere for å koble mellom elementene.
Heaps utfører flere operasjoner, inkludert:
- Finn-maks: søker etter den høyeste nøkkelnoden blant en gruppe noder
- Finn-min: Søker etter den laveste nøkkelnoden blant en gruppe noder
- Delete-max: Sletter den høyeste nøkkelnoden blant en gruppe noder
- Delete-min: Sletter den laveste nøkkelnoden blant en gruppe noder
Heaps inkluderer også funksjoner som utfører sammenslåing, innsetting og nøkkelendringer.
Denne definisjonen ble skrevet i sammenheng med Datastruktur
