Phenquestions
Illustrasjon av haugdatastrukturer
Det er to typer dynger: en maks-haug og en min-haug. En maks-haug-struktur er der den maksimale verdien er roten, og verdiene blir mindre etter hvert som treet stiger ned; enhver forelder er enten lik eller større i verdi enn noen av sine nærmeste barn. En min-haug-struktur er der minimumsverdien er roten, og verdiene blir større etter hvert som treet stiger ned; enhver forelder er enten lik eller mindre i verdi enn noen av sine nærmeste barn. I følgende diagrammer er den første en maks-haug og den andre er en min-haug:
For begge hauger, legg merke til at for et par barn, spiller det ingen rolle om den til venstre er den større verdien. En rad i et nivå i treet, må ikke nødvendigvis fylles fra minimum til maksimum, fra venstre; den fylles ikke nødvendigvis fra maksimum til minimum, fra venstre.
Representerer en haug i en matrise
For at programvare skal kunne bruke en haug enkelt, må haugen være representert i en matrise. Maks-haugen ovenfor, representert i en matrise er:
89, 85, 87, 84, 82, 79, 73, 80, 81,,, 65, 69Dette gjøres og begynner med rotverdien som den første verdien for matrisen. Verdiene plasseres kontinuerlig ved å lese treet fra venstre til høyre, fra topp til bunn. Hvis et element er fraværende, hoppes det over posisjonen i matrisen. Hver node har to barn. Hvis en node er ved indeks (posisjon) n, er dens første barn i matrisen ved indeks 2n + 1, og neste barn er ved indeks 2n + 2. 89 er ved indeks 0; sitt første barn, 85 er i indeks 2 (0) + 1 = 1 mens det andre barnet er i indeks 2 (0) + 2 = 2. 85 er ved indeks 1; sitt første barn, 84, er i indeks 2 (1) + 1 = 3 mens det andre barnet, 82 er i indeks 2 (1) + 2 = 4. 79 er på indeks 5; sitt første barn, 65 er i indeks 2 (5) + 1 = 11 mens det andre barnet er i indeks 2 (5) + 2 = 12. Formlene brukes på resten av elementene i matrisen.
En slik matrise, hvor betydningen av et element og forholdet mellom elementene, er underforstått av elementets posisjon, kalles en implisitt datastruktur.
Den implisitte datastrukturen for ovennevnte min-heap er:
65, 68, 70, 73, 71, 83, 84,,, 79, 80,,, 85, 89Ovennevnte max-heap er et komplett binært tre, men ikke et fullt binært tre. Det er derfor noen steder (posisjoner) er tomme i matrisen. For et fullstendig binært tre vil ingen plassering være tom i matrisen.
Nå, hvis haugen var et nesten komplett tre, for eksempel hvis verdien 82 manglet, ville matrisen være:
89, 85, 87, 84,, 79, 73, 80, 81,,, 65, 69I denne situasjonen er tre steder tomme. Imidlertid er formlene fortsatt gjeldende.
Operasjoner
En datastruktur er et dataformat (f.eks.g. et tre), pluss forholdet mellom verdiene, pluss operasjonene (funksjonene) som utføres på verdiene. For en haug er forholdet som går gjennom hele haugen, at foreldrene må være lik eller større i verdi enn barna, for en maks-haug; og foreldrene må være lik eller mindre i verdi enn barna, for en min-haug. Dette forholdet kalles haugegenskapen. Driften av en haug er gruppert under overskriftene Creation, Basic, Internal og Inspection. Et sammendrag av haugens operasjoner følger:
Heap Operations Sammendrag
Det er visse programvareoperasjoner som er vanlige med dynger, som følger:
Opprettelse av en haug
create_heap: Å lage en haug betyr å danne et objekt som representerer haugen. På C-språket kan du lage en haug med strukturtypen. Et av medlemmene i strukturen vil være heap array. Resten av medlemmene vil være funksjoner (operasjoner) for dyngen. Create_heap betyr å opprette en tom haug.
Heapify: Heap-arrayet er en delvis sortert (ordnet) array. Heapify betyr, gi et heap-array fra et usortert array - se detaljer nedenfor.
Slå sammen: Dette betyr å danne en fagbunke fra to forskjellige dynger - se detaljer nedenfor. De to haugene skal begge være max-heap eller begge min-heap. Den nye dyngen er i samsvar med haugegenskapen, mens de originale haugene er bevart (ikke slettet).
Meldt: Dette betyr at du kan bli med i to dynger av samme type for å danne en ny, og opprettholde duplikater - se detaljer nedenfor. Den nye dyngen er i samsvar med haugegenskapen, mens de opprinnelige dyngene blir ødelagt (slettet). Hovedforskjellen mellom sammenslåing og sammensmelting er at for sammensmelting passer det ene treet som et undertre til roten til det andre treet, slik at dupliserte verdier i det nye treet, mens for sammenslåing dannes et nytt dyngetre som fjerner duplikater. Det er ikke nødvendig å vedlikeholde de to originale dyngene med melding.
Grunnleggende haugoperasjoner
find_max (find_min): Finn maksimumsverdien i maks-heap-arrayet og returner en kopi, eller finn minimumsverdien i min-heap-arrayet og returner en kopi.
Sett inn: Legg til et nytt element i heap-arrayet, og omorganiser arrayet slik at heap-egenskapen i diagrammet opprettholdes.
extract_max (extract_min): Finn maksimumsverdien i max-heap-matrisen, fjern og returner den; eller finn minimumsverdien i min-heap-matrisen, fjern og returner den.
delete_max (delete_min): Finn rotnoden til en max-heap, som er det første elementet i max-heap-arrayet, fjern den uten å nødvendigvis returnere den; eller finn rotnoden til en min-haug, som er det første elementet i min-haug-matrisen, fjern den uten å nødvendigvis returnere den;
Erstatt: Finn rotnoden til en av haugene, fjern den og erstatt den med en ny. Det spiller ingen rolle om den gamle roten returneres.
Intern haugdrift
øke_nøkkel (redusere_nøkkel): Øk verdien på en hvilken som helst node for en maks-heap og omorganiser slik at heap-eiendommen opprettholdes, eller reduser verdien på en hvilken som helst node for en min-heap og omorganiser slik at heap-eiendommen opprettholdes.
Slett: slett en hvilken som helst node, og deretter omorganisere, slik at heap-eiendommen opprettholdes for maks-heap eller en min-heap.
shift_up: flytt en node opp i en maks-heap eller min-heap så lenge det er nødvendig, og omorganisere for å opprettholde heap-eiendommen.
shift_down: flytt en node ned i en maks-heap eller min-heap så lenge det er nødvendig, og omorganisere for å opprettholde heap-eiendommen.
Inspeksjon av en haug
Størrelse: Dette returnerer antall nøkler (verdier) i en bunke; den inkluderer ikke de tomme stedene i haugoppstillingen. En bunke kan vises med kode, som i diagrammet, eller med en matrise.
er tom: Dette returnerer boolsk sant hvis det ikke er noen node i en bunke, eller boolsk falsk hvis bunken har minst en node.
Sikt i en haug
Det er sikt opp og sikt ned:
Sift-Up: Dette betyr å bytte en node med sin overordnede. Hvis haugegenskapen ikke er fornøyd, bytter du forelderen med sin egen foreldre. Fortsett denne veien til stien til haugen er fornøyd. Fremgangsmåten kan komme til roten.
Sift ned: Dette betyr å bytte en node av stor verdi med den minste av de to barna (eller ett barn for en nesten full haug). Hvis haugegenskapen ikke er oppfylt, bytter du den nedre noden med den mindre noden til sine egne to barn. Fortsett denne veien i stien til haugegenskapen er fornøyd. Fremgangsmåten kan nå et blad.
Heapifying
Heapify betyr å sortere en usortert matrise for å ha heap-eiendommen tilfredsstilt for maks-heap eller min-heap. Dette betyr at det kan være noen tomme steder i den nye matrisen. Den grunnleggende algoritmen for å heapify en max-heap eller min-heap er som følger:
- hvis rotnoden er mer ekstrem enn en av barnets noder, så bytt roten med den mindre ekstreme undernoden.
- Gjenta dette trinnet med barnenodene i et forhåndsbestillingsskjema for treovergang.
Det siste treet er et haugetre som tilfredsstiller haugegenskapen. En haug kan vises som et trediagram eller i en matrise. Den resulterende dyngen er et delvis sortert tre, dvs.e. en delvis sortert matrise.
Heap Operation Detaljer
Denne delen av artikkelen gir detaljene om dyngoperasjonene.
Opprettelse av en haugdetaljer
create_heap
Se ovenfor!
heapify
Se ovenfor
slå sammen
Hvis haugen arrays,
89, 85, 87, 84, 82, 79, 73, 80, 81,,, 65, 69og
89, 85, 84, 73, 79, 80, 83, 65, 68, 70, 71blir slått sammen, kan resultatet uten duplikater være,
89, 85, 87, 84, 82, 83, 81, 80, 79,, 73, 68, 65, 69, 70, 71Etter litt sikting. Legg merke til at 82 ikke har barn i den første matrisen. I den resulterende matrisen er den ved indeks 4; og dens plasseringer ved indeks 2 (4) + 1 = 9 og 2 (4) + 2 = 10 er ledige. Dette betyr at det heller ikke har barn i det nye tre-diagrammet. De to originale haugene bør ikke slettes, siden informasjonen deres ikke er i den nye bunken (ny matrise). Den grunnleggende algoritmen for å slå sammen dynger av samme type er som følger:
- Bli med en matrise til bunnen av den andre matrisen.
- Heapify eliminerer duplikater, og sørger for at noder som ikke hadde barn i de opprinnelige dyngene, fortsatt ikke har barn i den nye dyngen.
meld
Algoritmen for å smelte to dynger av samme type (enten to maks- eller to min-) er som følger:
- Sammenlign de to rotnodene.
- Lag den mindre ekstreme roten og resten av treet (undertreet), det andre barnet til den ekstreme roten.
- Sikt det bortkomne barnet av roten til nå det ekstreme undertreet, nedover i det ekstreme undertreet.
Den resulterende dyngen er fortsatt i samsvar med haugegenskapen, mens de opprinnelige dyngene blir ødelagt (slettet). De opprinnelige dyngene kan bli ødelagt fordi all informasjonen de hadde, fremdeles er i den nye dyngen.
Grunnleggende haugoperasjoner
find_max (find_min)
Dette betyr å finne maksimumsverdien i max-heap-arrayet og returnere en kopi, eller lokalisere minimumsverdien i min-heap-arrayet og returnere en kopi. En haugmatrise per definisjon tilfredsstiller allerede haugegenskapen. Så bare returner en kopi av det første elementet i matrisen.
sett inn
Dette betyr at du legger til et nytt element i heap-arrayet, og omorganiserer arrayet slik at heap-egenskapen i diagrammet opprettholdes (tilfreds). Algoritmen for å gjøre dette for begge typer dynger er som følger:
- Anta et fullt binært tre. Dette betyr at matrisen må fylles til slutt med tomme steder om nødvendig. Totalt antall noder for en full haug er 1, eller 3 eller 7 eller 15 eller 31 osv.; fortsett å doble og legge til 1.
- Sett noden på det mest egnede tomme stedet etter størrelse, mot slutten av dyngen (mot slutten av haugoppstillingen). Hvis det ikke er noe tomt sted, så start en ny rad nederst til venstre.
- Sikt opp om nødvendig til haugegenskapen er fornøyd.
extract_max (extract_min)
Finn maksimumsverdien i maks-heap-matrisen, fjern og returner den; eller finn minimumsverdien i min-heap-matrisen, fjern og returner den. Algoritmen til extract_max (extract_min) er som følger:
- Fjern rotnoden.
- Ta (fjern) den nederste høyre noden (siste node i matrisen) og plasser den ved roten.
- Sikt ned etter behov, til haugegenskapen er fornøyd.
delete_max (delete_min)
Finn rotnoden til en max-heap, som er det første elementet i max-heap-arrayet, fjern den uten å nødvendigvis returnere den; eller finn rotnoden til en min-haug, som er det første elementet i min-haug-matrisen, fjern den uten å nødvendigvis returnere den. Algoritmen for å slette rotnoden er som følger:
- Fjern rotnoden.
- Ta (fjern) den nederste høyre noden (siste node i matrisen) og plasser den ved roten.
- Sikt ned etter behov, til haugegenskapen er fornøyd.
erstatte
Finn rotnoden til en av haugene, fjern den og erstatt den med den nye. Det spiller ingen rolle om den gamle roten returneres. Sikt ned hvis det er hensiktsmessig, til haugegenskapen er fornøyd.
Intern haugdrift
økningstast (nedgangstast)
Øk verdien på en hvilken som helst node for en maks-heap og omorganiser slik at heap-egenskapen opprettholdes, eller reduser verdien på en hvilken som helst node for en min-heap og omorganiser slik at heap-eiendommen opprettholdes. Sikt opp eller ned etter behov, til haugegenskapen er fornøyd.
slett
Fjern noden som er av interesse, og deretter omorganisere, slik at haugegenskapen opprettholdes for maks-haugen eller en min-haug. Algoritmen for å slette en node er som følger:
- Fjern noden av interesse.
- Ta (fjern) den nederste høyre noden (siste node i matrisen) og plasser ved indeksen til noden som er fjernet. Hvis noden som er slettet, er på den siste raden, er dette kanskje ikke nødvendig.
- Sikt opp eller ned etter behov, til haugegenskapen er fornøyd.
gire opp
Flytt en node opp i en maks- eller min-haug så lenge det er nødvendig, og omorganisere for å opprettholde haugegenskapen - sikt opp.
Gir ned
Flytt en node ned i en maks-heap eller min-heap så lenge som nødvendig, og omorganiser for å opprettholde heap-eiendommen - sikt ned.
Inspeksjon av en haug
størrelse
Se ovenfor!
er tom
Se ovenfor!
Andre klasser av dynger
Haugen beskrevet i denne artikkelen kan betraktes som den viktigste (generelle) haugen. Det er andre klasser av dynger. Imidlertid er de to som du bør vite utover dette Binary Heap og d-ary Heap.
Binær haug
Den binære bunken ligner på denne hovedbunken, men med flere begrensninger. Spesielt må den binære dyngen være et komplett tre. Ikke forveksle mellom et komplett tre og et fullt tre.
d-ary Haug
En binær haug er en to-arig haug. En haug der hver node har 3 barn er en 3-arig haug. En haug der hver node har 4 barn er en 4-arig haug, og så videre. En d-ar haug har andre begrensninger.
Konklusjon
En haug er et komplett eller nesten komplett binært tre som tilfredsstiller haugegenskapen. Haugegenskapen har to alternativer: for en maks-haug må en forelder være lik eller større i verdi enn de nærmeste barna; for en minhaug må en forelder være lik eller mindre i verdi enn de nærmeste barna. En haug kan vises som et tre eller i en matrise. Når den er representert i en matrise, er rotnoden den første noden i matrisen; og hvis en node er ved indeks n, er det første barnet i matrisen ved indeks 2n + 1 og neste barn er ved indeks 2n + 2. En haug har visse operasjoner som utføres på matrisen.
Chrys
