Hevedatastrukturopplæring

Data er et sett med verdier. Data kan samles og settes på rad, eller i en kolonne, eller i en tabell eller i form av et tre. Datastrukturen er ikke bare plassering av data i noen av disse formene. I databehandling er datastrukturen noen av disse formatene, pluss forholdet mellom verdiene, pluss operasjonene (funksjonene) utfører på verdiene. Du bør allerede ha grunnleggende kunnskap om tredatastruktur før du kommer hit, som konseptene der, vil bli brukt her med liten eller ingen forklaring. Hvis du ikke har den kunnskapen, kan du lese opplæringen med tittelen, Tree Data Structure Tutorial for Nybegynnere, på lenken, https: // Linuxhint.com/tree_data_structure_tutorial_beginners/. Etter det, fortsett å lese denne opplæringen.En damedatastruktur er et komplett eller nesten komplett binært tre, der barnet til hver node er lik eller mindre i verdi enn verdien av foreldrene. Alternativt er det et slikt tre der verdien av en forelder er lik eller mindre enn verdien av noen av barna. Verdien (Datum) til et tre kalles også nøkkelen.

Illustrasjon av HAP -datastrukturer

Det er to typer hauger: en maksimal og en min-heap. En maksimal struktur er der maksimalverdien er roten, og verdiene blir mindre etter hvert som treet er avstammet; Enhver forelder er enten lik eller større i verdi enn noen av de umiddelbare barna. En min-heap-struktur er der minimumsverdien er roten, og verdiene blir større etter hvert som treet er avstammet; Enhver forelder er enten lik eller mindre i verdi enn noen av de umiddelbare barna. I de følgende diagrammer er det første en maksimal og den andre er en min-heap:

For begge hauger, legg merke til at det for et par barn ikke spiller noen 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; Det er ikke nødvendigvis fylt fra maksimum til minimum, fra venstre.

Representerer en haug i en matrise

For at programvare enkelt skal bruke en haug, må haugen være representert i en matrise. Max-heap ovenfor, representert i en matrise er:

89, 85, 87, 84, 82, 79, 73, 80, 81 ,,, 65, 69

Dette gjøres fra og 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, blir dens posisjon i matrisen hoppet over. Hver node har to barn. Hvis en node er i indeks (posisjon) n, er det første barnet i matrisen ved indeks 2n+1, og dets neste barn er ved indeks 2n+2. 89 er ved indeks 0; Det første barnet, 85 er ved indeks 2 (0)+1 = 1 mens det andre barnet er ved indeks 2 (0)+2 = 2. 85 er ved indeks 1; Det første barnet, 84, er ved indeks 2 (1)+1 = 3 mens det andre barnet, 82 er ved indeks 2 (1)+2 = 4. 79 er ved indeks 5; Det første barnet, 65 er ved indeks 2 (5)+1 = 11 mens det andre barnet er ved indeks 2 (5)+2 = 12. Formlene brukes på resten av elementene i matrisen.

En slik rekke, der betydningen av et element og forholdet mellom elementene, antydes av elementets plassering, kalles en implisitt datastruktur.

Den implisitte datastrukturen for ovennevnte min-heap er:

65, 68, 70, 73, 71, 83, 84 ,,, 79, 80 ,, 85, 89

Ovennevnte max-heap er et komplett binært tre, men ikke et fullt binært tre. Det er grunnen til at noen steder (posisjoner) er tomme i matrisen. For et fullt binært tre vil ingen beliggenhet være tomt i matrisen.

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, 69

I denne situasjonen er tre steder tomme. Imidlertid er formlene fortsatt anvendelige.

Operasjoner

En datastruktur er et format av data (e.g. et tre), pluss forholdet mellom verdiene, pluss operasjonene (funksjonene) utfører på verdiene. For en haug er forholdet som går gjennom hele haugen, at forelderen må være like eller større i verdi enn barna, for en maksimal hau; og forelderen må være like eller mindre i verdi enn barna, for en mineap. Dette forholdet kalles Heap -eiendommen. Operasjon av en haug er gruppert under skaperverdiene, grunnleggende, interne og inspeksjonen. Et sammendrag av driften av haugen følger:

HAP -operasjonssammendrag

Det er visse programvareoperasjoner som er vanlige med hauger, 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 opprette en haug med Struct Object -typen. Et av medlemmene i strukturen vil være Heap -matrisen. Resten av medlemmene vil være funksjoner (operasjoner) for haugen. Create_heap betyr å lage en tom haug.

Heapify: Heap -arrayen er en delvis sortert (bestilt) matrise. Heapify betyr, gi en haug -matrise fra en usortert matrise - se detaljer nedenfor.

Fusjon: Dette betyr, danner en unions haug fra to forskjellige hauger - se detaljer nedenfor. De to dyngene skal begge være maksimal eller begge min-heap. Den nye haugen er i samsvar med Heap -eiendommen, mens de opprinnelige dyngene er bevart (ikke slettet).

MELD: Dette betyr, bli med to hauger av samme type for å danne en ny, vedlikeholde duplikater - se detaljer nedenfor. Den nye haugen er i samsvar med Heap -eiendommen, mens de opprinnelige hauene blir ødelagt (slettet). Hovedforskjellen mellom sammenslåing og smelting er at for smelting passer ett tre som en undertrekk til roten til det andre treet, slik at duplikatverdier i det nye treet, mens for sammenslåing dannes et nytt haupertre, og fjerner duplikater. Det er ikke nødvendig å opprettholde de to originale dyngene med smelting.

Grunnleggende haugoperasjoner

find_max (find_min): Finn maksimalverdien i max-heap-arrayen og returner en kopi, eller finn minimumsverdien i min-heap-matrisen og returner en kopi.

Sett inn: Legg til et nytt element i HAP -matrisen, og omorganiserer matrisen slik at diagrammets haugegenskap blir opprettholdt.

EXTRACT_MAX (EXTRACT_MIN): Finn maksimalverdien i Max-Heap-arrayen, 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-matrisen, fjern den uten nødvendigvis å returnere den; eller finn rotnoden til en min-heap, som er det første elementet i min-heap-arrayen, 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 blir returnert.

Intern heapoperasjoner

øke_key (reduksjon_key): Øk verdien av en hvilken som helst node for en maksimal og omorganiserer slik at heapegenskapen opprettholdes, eller reduser verdien av en node for en min-heap og omorganiserer slik at heapegenskapen opprettholdes.

Slett: Slett en hvilken som helst node, deretter omorganiser, slik at heapegenskapen opprettholdes for max-heap eller en min-heap.

Shift_up: Flytt en node opp i en maksimal eller min-heap så lenge som nødvendig, og omorganiser for å opprettholde Heap-eiendommen.

Shift_down: Flytt en node ned i en maksimal eller min-heap så lenge som nødvendig, og omorganiser for å opprettholde Heap-eiendommen.

Inspeksjon av en haug

Størrelse: Dette returnerer antall nøkler (verdier) i en haug; Det inkluderer ikke de tomme plasseringene av Heap -matrisen. En haug kan være representert med kode, som i diagrammet, eller med en matrise.

er tom: Dette returnerer boolsk sann hvis det ikke er noen node i en haug, eller boolsk falsk hvis haugen har minst en node.

Sift i en haug

Det er sikt opp og sile ned:

Sift-up: Dette betyr å bytte en node med foreldrene. Hvis Heap -eiendommen ikke er fornøyd, bytter du foreldrene med sin egen forelder. Fortsett denne veien i banen til Heap -eiendommen er fornøyd. Prosedyren kan nå roten.

Sift-down: Dette betyr å bytte en node med stor verdi med den mindre av de to barna (eller ett barn for en nesten fullstendig haug). Hvis Heap -egenskapen ikke er fornøyd, bytter du den nedre noden med den mindre noden til sine egne to barn. Fortsett denne veien i banen til Heap -eiendommen er fornøyd. Prosedyren kan nå et blad.

Hauger

Heapify betyr å sortere en usortert matrise for å ha Heap-eiendommen fornøyd for maksimal eller min-heap. Dette betyr at det kan være noen tomme steder i den nye matrisen. Den grunnleggende algoritmen for å ha en maksimal eller min-heap er som følger:

- Hvis rotnoden er mer ekstrem enn noen av barnets node, kan du bytte roten med den mindre ekstreme barneknuten.

- Gjenta dette trinnet med barneknuter i et forhåndsbestill tre som krysser ordningen.

Det endelige treet er et høstre som tilfredsstiller Heap -eiendommen. En haug kan bli representert som et trediagram eller i en matrise. Den resulterende haugen er et delvis sortert tre, jeg.e. en delvis sortert matrise.

DETALJERINGER

Denne delen av artikkelen gir detaljer om haugoperasjonene.

Opprettelse av en haugdetaljer

create_heap

Se ovenfor!

Heapify

Se ovenfor

slå sammen

Hvis haugene er,

89, 85, 87, 84, 82, 79, 73, 80, 81 ,,, 65, 69

og

89, 85, 84, 73, 79, 80, 83, 65, 68, 70, 71

blir slått sammen, resultatet uten duplikater kan være,

89, 85, 87, 84, 82, 83, 81, 80, 79 ,, 73, 68, 65, 69, 70, 71

Etter litt sikt. Legg merke til at i den første matrisen har 82 ingen barn. I den resulterende matrisen er det ved indeks 4; og plasseringen av indeks 2 (4)+1 = 9 og 2 (4)+2 = 10 er ledige. Dette betyr at det heller ikke har barn i det nye trediagrammet. De originale to hauger skal ikke slettes siden informasjonen ikke egentlig er i den nye haugen (ny matrise). Den grunnleggende algoritmen for å slå sammen hauger av samme type er som følger:

- Bli med på den ene matrisen til bunnen av den andre matrisen.

- Heapify eliminerer duplikater, og sørger for at noder som ikke hadde barn i den opprinnelige haugen, fremdeles ikke har barn i den nye haugen.

Meld

Algoritmen for å smelte sammen to hauger av samme type (enten to max- eller to min-) er som følger:

- Sammenlign de to rotnodene.

- Lag den mindre ekstreme rot og resten av treet (subtree), det andre barnet av den ekstreme roten.

- Sikt det omstreifende barnet til roten til nå den ekstreme undertrekk, nedover i ekstreme undertree.

Den resulterende haugen er fremdeles i samsvar med Heap -eiendommen, mens de opprinnelige dyngene blir ødelagt (slettet). De originale dyngene kan bli ødelagt fordi all informasjonen de hadde fremdeles er i den nye haugen.

Grunnleggende haugoperasjoner

find_max (find_min)

Dette betyr å lokalisere maksimalverdien i max-heap-matrisen og returnere en kopi, eller finne minimumsverdien i min-heap-matrisen og returnere en kopi. En haugesett per definisjon tilfredsstiller allerede Heap -eiendommen. Så bare returner en kopi av det første elementet i matrisen.

sett inn

Dette betyr å legge til et nytt element i Heap -matrisen, og omorganisere matrisen slik at diagrammets haugegenskap opprettholdes (fornøyd). Algoritmen for å gjøre dette for begge typer hauger er som følger:

- Anta et fullt binært tre. Dette betyr at matrisen må fylles på slutten med tomme steder om nødvendig. Det totale antallet noder av 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 passende tomme stedet etter størrelsesorden, mot slutten av haugen (mot slutten av heap -arrayen). Hvis det ikke er noen tom plassering, så start en ny rad nederst til venstre.

- Sikt opp om nødvendig, til Heap -eiendommen er fornøyd.

Extract_Max (Extract_min)

Finn den maksimale verdien i Max-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 til høyre noden (siste node i matrisen) og legg ved roten.

- Sikt ned etter behov, til Heap -eiendommen er fornøyd.

delete_max (Delete_min)

Finn rotnoden til en max-heap, som er det første elementet i max-heap-arrayen, fjern den uten nødvendigvis å returnere den; eller finn rotnoden til en min-heap, som er det første elementet i min-heap-matrisen, fjern den uten nødvendigvis å returnere den. Algoritmen for å slette rotnoden er som følger:

- Fjern rotnoden.

- Ta (fjern) den nederste til høyre noden (siste node i matrisen) og legg ved roten.

- Sikt ned etter behov, til Heap -eiendommen 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 blir returnert. Sikt ned hvis det er aktuelt, til Heap -eiendommen er fornøyd.

Intern heapoperasjoner

øke_key (reduksjon_key)

Øk verdien av en hvilken som helst node for en maksimal og omorganiserer slik at Heap-egenskapen opprettholdes, eller reduser verdien av en hvilken som helst node for en min-heap og omorganiserer slik at Heap-egenskapen opprettholdes. Sikt opp eller ned etter behov, til Heap -eiendommen er fornøyd.

slett

Fjern noden av interesse, deretter omorganiser, slik at Heap-eiendommen opprettholdes for maksimalen eller en min-heap. Algoritmen for å slette en node er som følger:

- Fjern interessen for interesse.

- Ta (fjern) den nederste til høyre noden (siste node i matrisen) og legg ved indeksen for noden fjernet. Hvis noden som er slettet er på siste rad, kan det hende at dette ikke er nødvendig.

- Sikt opp eller ned etter behov, til Heap -eiendommen er fornøyd.

gire opp

Flytt en node opp i en max-heap eller min-heap så lenge som nødvendig, og omorganiser for å opprettholde Heap-eiendommen-sikt opp.

Gir ned

Flytt en node ned i en max-heap eller min-heap så lenge som nødvendig, og omorganiser for å opprettholde Heap-eiendommen-SIFT ned.

Inspeksjon av en haug

størrelse

Se ovenfor!

er tom

Se ovenfor!

Andre klasser av hauger

Heapen beskrevet i denne artikkelen kan betraktes som hoved (generell) haug. Det er andre klasser av hauger. Imidlertid er de to som du bør vite utover dette, den binære haugen og D-Aar-haugen.

Binær haug

Den binære haugen ligner på denne viktigste haugen, men med flere begrensninger. Spesielt må den binære haugen være et komplett tre. Ikke forveksle mellom et komplett tre og et fullt tre.

d-ary haug

En binær haug er en 2-ary haug. En haug der hver node har 3 barn er en 3-ary haug. En haug der hver node har 4 barn er en 4-ary haug, og så videre. En d-ary haug har andre begrensninger.

Konklusjon

En haug er et komplett eller nesten komplett binært tre, som tilfredsstiller Heap -eiendommen. Heap-eiendommen har 2 alternativer: For en maksimal må en forelder være like eller større i verdi enn de umiddelbare barna; For en min-heap må en forelder være like eller mindre i verdi enn de umiddelbare barna. En haug kan bli representert som et tre eller i en matrise. Når den er representert i en matrise, er rotnoden den første noden til matrisen; Og hvis en node er ved indeks n, er det første barnet i matrisen ved indeks 2n+1 og dets neste barn er ved indeks 2n+2. En haug har visse operasjoner som utføres på matrisen.

Chrys