Binære hauger i JavaScript
Heap -eiendommen
Denne egenskapen kan betraktes som en begrensning for å definere et tre, en viss struktur som må følges mens du konstruerer et tre. Heap definerer et forhold mellom overordnede noder og dens barneknuter, det er to typer hauger, og det er derfor to typer forhold som kan eksistere mellom foreldroden og barneknuten:
- Max-heap: Verdien av overordnede noder må alltid være større eller lik barneknutene
- Min-heap: Verdien av overordnede noder må alltid være mindre eller lik barneknutene
En representasjon av Min-Heap er:
(Bilde av Wikipedia)
Som du kan se, i treet at foreldrodene har lavere verdier enn deres barneknuter
AR-representasjon av Max-Heap er:
(Bilde av Wikipedia)
Du kan se at foreldrodene har verdier større enn barneknuter.
Array -representasjon
Heaps på et programmeringsspråk er representert i form av en matrise, et eksempel på haugesarrayen konstruert fra max-heap-treet over er:
var max-heap = [100,19,36,17,3,25,1,2,7];Når du representerer en binær haug i form av en matrise, bruker du følgende uttrykk for å utlede følgende:
- Venstre barn = i * 2
- Høyre barn = i * 2 + 1
- Foreldre = i / 2
Hvor "Jeg" står for indeksen for matrisen. Snakker om indekser, når vi implementerer haugestrukturer ved hjelp av en matrise, legger vi en "null" I den første indeksen som er indeksen 0.
Visuell representasjon av å jobbe av en haug
For en virtuell representasjon av arbeidet med en min-heap og hvordan blir verdiene satt inn i haugen, kan vi ta turen til haugen visualisator av University of San Francisco ved å klikke her
Sett inn verdier i haugen, og du vil merke hvordan et nytt element settes inn i haugen på grunn av animasjonen:
Arbeider med haug
En binær haug har to hovedfunksjoner:
- Først er det å legge til det nye elementet i passende posisjon
- Den andre funksjonen er å fjerne rotverdien
Legge til et nytt element i haugen
Et nytt element blir alltid lagt til på slutten av matrisen, og deretter blir det sjekket mot foreldrene, og hvis det strider mot Heap -eiendommen, blir det utvekslet med foreldrene. Elementet blir sjekket til det er sammenlignet med rotteknuten til heapen (rotnoden er den første noden til haugen).
Fjerne et element fra haugen
Hver gang du vil fjerne eller hente en verdi fra haugen, henter du alltid rotknutens verdi. Det er grunnen til at denne verdien er den minste verdien hvis den er en min-heap og den største verdien hvis den er en maksimal heap. Når rotnoden fjernes fra haugen, tar den siste noden til matrisen sin plass, så blir den sammenlignet med barneknuter for å matche tilstanden til haugen. Hvis den ikke samsvarer med tilstanden, erstattes den med barneknuten og deretter sjekket med ytterligere barneknuter. En mye bedre måte å forklare dette på er ved å bruke den levende Heap -seeren som vist nedenfor:
Du kan observere fjerningsprosessen ved å observere GIF over.
Implementering av den binære haugen i JavaScript
Vi kommer til å implementere min-heap trinn for trinn, vi starter prosessen ved å lage en ny funksjon med følgende kodelinjer:
La minheap = funksjon ()// resten av min-heap-koden vil være til stede
Det første trinnet er å opprette en matrise og angi verdien til indeksen 0 som null:
La heap = [null];
Så skal vi lage Sett inn funksjon Bruke følgende kodelinjer:
dette.Sett inn = funksjon (num)
haug.push (num);
hvis (haug.lengde> 2)
LetidX = haug.lengde - 1;
mens (haug [idx] = 1)
[haug [matematikk.gulv (idx / 2)], heap [idx]] = [
Heap [IDX],
haug [matematikk.gulv (idx / 2)],
];
hvis (matematikk.gulv (idx / 2)> 1)
IDX = matematikk.gulv (IDX / 2);
annet
gå i stykker;
;
Følgende ting skjer i dette kodebiten:
- Et nytt element Num blir lagt til i den siste indeksen for matrisen
- Hvis matriselengden er større enn 2 elementer, sjekker vi det nye elementet med foreldroden
- Hvis elementet er mindre enn den overordnede noden, erstattes det med foreldroden, ellers trekker vi ut at haugen i riktig rekkefølge
- Hvis elementet erstattes med foreldroden i forrige trinn, sammenligner vi det igjen med den nye forelderen til vi trekker ut at haugen er i riktig rekkefølge eller elementet blir rotnoden
Neste trinn er å implementere Fjern funksjonen med følgende kodelinjer:
dette.Fjern = funksjon ()La minste = haug [1];
hvis (haug.lengde> 2)
haug [1] = haug [haug.lengde - 1];
haug.Splice (haug.lengde - 1);
hvis (haug.lengde == 3)
if (haug [1]> haug [2])
[haug [1], haug [2]] = [haug [2], haug [1]];
returnerer minste;
leti = 1;
letleft = 2 * i;
letright = 2 * i + 1;
mens (haug [i]> = haug [venstre] || haug [i]> = haug [til høyre])
if (haug [til venstre] < heap[right])
[haug [i], haug [venstre]] = [heap [venstre], haug [i]];
i = 2 * i;
annet
[haug [i], haug [til høyre]] = [heap [til høyre], haug [i]];
i = 2 * i + 1;
venstre = 2 * i;
høyre = 2 * i + 1;
if (heap [venstre] == udefinert || heap [til høyre] == udefinert)
gå i stykker;
elseif (haug.lengde == 2)
haug.skjøte (1, 1);
annet
return null;
returnerer minste;
;
Følgende trinn skjer i ovennevnte kodebit:
- Vi fjerner rotknuten da den er den minste noden til haugen
- Hvis heapen bare har to elementer, blir det andre elementet rotnoden
- Hvis dyngen har 3 elementer, blir den minste av 2. og 3. element rotnoden
- Hvis elementet har mer enn 3 elementer, blir det siste elementet i haugen rotnoden
- Deretter blir denne nye rotnoden sammenlignet med barneknuter og erstattes med den mindre noden og er imot sammenlignet med de nye barneknuter (for erstatning bruker vi Objekt Destructuring Method)
- Denne prosessen med å sammenligne elementet med barneknuter gjentas til det når et punkt der det er mindre enn begge barneknutene eller det blir den siste noden i matrisen.
Neste trinn er å lage en funksjon som viser oss HAP -matrisen til konsollen, vi gjør det ved å bruke følgende kodelinjer:
dette.show = funksjon ()konsoll.logg (heap);
;
Det komplette kodebitet for å implementere min-heap-datastrukturen er:
letminheap = funksjon ()La heap = [null];
dette.Sett inn = funksjon (num)
haug.push (num);
hvis (haug.lengde> 2)
LetidX = haug.lengde - 1;
mens (haug [idx] = 1)
[haug [matematikk.gulv (idx / 2)], heap [idx]] = [
Heap [IDX],
haug [matematikk.gulv (idx / 2)],
];
hvis (matematikk.gulv (idx / 2)> 1)
IDX = matematikk.gulv (IDX / 2);
annet
gå i stykker;
;
dette.Fjern = funksjon ()
La minste = haug [1];
hvis (haug.lengde> 2)
haug [1] = haug [haug.lengde - 1];
haug.Splice (haug.lengde - 1);
hvis (haug.lengde == 3)
if (haug [1]> haug [2])
[haug [1], haug [2]] = [haug [2], haug [1]];
returnerer minste;
leti = 1;
La venstre = 2 * i;
La høyre = 2 * i + 1;
mens (haug [i]> = haug [venstre] || haug [i]> = haug [til høyre])
if (haug [til venstre] < heap[right])
[haug [i], haug [venstre]] = [heap [venstre], haug [i]];
i = 2 * i;
annet
[haug [i], haug [til høyre]] = [heap [til høyre], haug [i]];
i = 2 * i + 1;
venstre = 2 * i;
høyre = 2 * i + 1;
if (heap [venstre] == udefinert || heap [til høyre] == udefinert)
gå i stykker;
elseif (haug.lengde == 2)
haug.skjøte (1, 1);
annet
Returnnull;
returnerer minste;
;
dette.show = funksjon ()
konsoll.logg (heap);
;
;
Det vi trenger å gjøre nå er å lage en ny Min-Heap ved hjelp. For å gjøre dette lager vi en ny variabel og kartlegger den på minheapen ved å bruke følgende kodelinjer:
var newminheap = new Minheap ();Neste, la oss legge til verdier til haugen ved å bruke følgende kodelinjer:
Newminheap.sett inn (34);Newminheap.sett inn (61);
Newminheap.Sett inn (138);
Newminheap.sett inn (82);
Newminheap.sett inn (27);
Newminheap.sett inn (35);
Nå kaller vi forestilling Funksjon for å vise hauggruppen på konsollen:
Newminheap.forestilling();Vi får følgende resultat på konsollen vår:
Som du ser er det første elementet i matrisen null. Resten av nodene er ikke større enn deres barneknuter. For eksempel, hvis vi tar noden med verdien 35. Venstre og høyre barn er som:
Du kan tydelig se, foreldre (35) er mindre enn venstre barn (82) og dets rette barn (61) også. Tilsvarende er hver foreldrode mindre enn barneknuten, derfor kan vi utlede at koden vår fungerer perfekt
Tilsvarende ved bare å endre tilstanden for å sammenligne for å være overordnet nod som er mindre enn barnet med at overordnede noden er større enn barneknuten, kan vi implementere Max-heap Bruke følgende kodelinjer:
letMaxHeap = funksjon ()La heap = [null];
dette.Sett inn = funksjon (num)
haug.push (num);
hvis (haug.lengde> 2)
LetidX = haug.lengde - 1;
mens (haug [idx]> haug [matematikk.gulv (idx / 2)])
if (idx> = 1)
[haug [matematikk.gulv (idx / 2)], heap [idx]] = [
Heap [IDX],
haug [matematikk.gulv (idx / 2)],
];
hvis (matematikk.gulv (idx / 2)> 1)
IDX = matematikk.gulv (IDX / 2);
annet
gå i stykker;
;
dette.Fjern = funksjon ()
La minste = haug [1];
hvis (haug.lengde> 2)
haug [1] = haug [haug.lengde - 1];
haug.Splice (haug.lengde - 1);
hvis (haug.lengde == 3)
if (haug [1] < heap[2])
[haug [1], haug [2]] = [haug [2], haug [1]];
returnerer minste;
leti = 1;
La venstre = 2 * i;
La høyre = 2 * i + 1;
mens (haug [i] <= heap[left] || heap[i] heap[right])
[haug [i], haug [venstre]] = [heap [venstre], haug [i]];
i = 2 * i;
annet
[haug [i], haug [til høyre]] = [heap [til høyre], haug [i]];
i = 2 * i + 1;
venstre = 2 * i;
høyre = 2 * i + 1;
if (heap [venstre] == udefinert || heap [til høyre] == udefinert)
gå i stykker;
elseif (haug.lengde == 2)
haug.skjøte (1, 1);
annet
Returnnull;
returnerer minste;
;
dette.show = funksjon ()
konsoll.logg (heap);
;
;
Det er det, du har implementert en binær hauger i JavaScript
Konklusjon
Binære hauger er den parietale implementeringen av et binært tre som har betingelse av å ha på det meste To barneknuter for hver foreldrode, og den komplette strukturen til det binære treet. Noe som betyr at nivåene på treet vil bli fylt fra venstre eller venstre barn og deretter høyre barn.
Binære hauger er en del av avanserte datastrukturer, og det er to typer binært tre: en av dem kalles Min -haugen mens den andre kalles Max Heap. I Min-Heap har foreldrodene mindre verdier enn barneknuter, og verdiene til søskenknutene betyr ikke noe.
Tilsvarende, i Max-Heap, er verdiene til overordnede noden alltid større enn deres barneknute, og verdiene til søskenknutene betyr ikke noe. I dette innlegget lærte vi om hauger og deres implementering i Vanilla JavaScript, og på slutten testet vi ut implementeringen vår.