Binarne stosy w JavaScript
Właściwość sterta
Ta właściwość można uznać za ograniczenie definiowania drzewa, pewną strukturę, którą należy przestrzegać podczas konstruowania drzewa. Sterta określa związek między węzłami macierzystymi a jego węzłami dziecięcymi, istnieją dwa rodzaje sterty, a zatem istnieją dwa rodzaje relacji, które mogą istnieć między węzłem nadrzędnym a węzłem dziecięcym:
- Max-heap: wartość węzłów macierzystych musi być zawsze większa lub równa węzłom dziecięcym
- Min-heap: wartość węzłów macierzystych musi być zawsze mniejsza lub równa węzłom dziecięcym
Reprezentacja Min-Heap to:
(Image by Wikipedia)
Jak widać, w drzewie, że węzły macierzysty mają niższe wartości niż ich węzły dziecięce
Reprezentacja AR Max-heap to:
(Image by Wikipedia)
Widać, że węzły macierzyste mają wartości większe niż ich węzły dziecięce.
Reprezentacja tablicy
Płyty w języku programowania są reprezentowane w postaci tablicy, przykładem tablicy sterty skonstruowanej z powyższego drzewa maksymalnego heap jest:
var max-heap = [100,19,36,17,3,25,1,2,7];Reprezentując stertę binarną w postaci tablicy, używasz następującego wyrażenia, aby wydedukować następujące czynności:
- Lewe dziecko = i * 2
- Właściwe dziecko = i * 2 + 1
- Rodzic = I / 2
Gdzie "I" oznacza indeks tablicy. Mówiąc o indeksach, kiedy wdrażamy struktury sterty za pomocą tablicy, umieszczamy "zero" W pierwszym indeksie, którym jest indeks 0.
Wizualna reprezentacja pracy sterty
Aby uzyskać wirtualną reprezentację pracy min-heap i w jaki sposób wartości wkładane są do sterty, możemy udać się do wizualizatora sterty przez University of San Francisco, klikając tutaj
Włóż wartości do sterty, a zauważysz, w jaki sposób nowy element jest wstawiany do sterty z powodu animacji:
Działanie sterty
Sterta binarna ma dwie główne funkcje:
- Pierwszym z nich jest dodanie nowego elementu w jego odpowiednim położeniu
- Drugą funkcją jest usunięcie wartości głównej
Dodanie nowego elementu w stercie
Nowy element jest zawsze dodawany na końcu tablicy, a następnie jest sprawdzany przeciwko jego rodzicielowi, a jeśli jest on sprzeczny z właściwością sterty, jest wymieniany ze swoim rodzicem. Element jest sprawdzany, aż zostanie porównany z węzłem głównym sterty (węzeł główny jest pierwszym węzłem sterty).
Usuwanie elementu z sterty
Ilekroć chcesz usunąć lub pobrać wartość z sterty, zawsze pobierasz wartość węzła głównego. Dlatego ta wartość jest najmniejszą wartością, jeśli jest to minima i największa wartość, jeśli jest to maksymalnie. Gdy węzeł główny jest usuwany z sterty, ostatni węzeł tablicy zajmuje jego miejsce, wówczas jest porównywany z węzłami dziecięcymi, aby pasować do stanu sterty. Jeśli nie pasuje do tego warunku, jest zastępowany węzłem dziecięcym, a następnie sprawdzany za pomocą dalszych węzłów dziecięcych. O wiele lepszym sposobem na wyjaśnienie tego jest użycie przeglądarki Live Heap, jak pokazano poniżej:
Możesz zaobserwować proces usuwania, obserwując powyższy GIF.
Wdrażanie sterty binarnej w JavaScript
Będziemy wdrażać minim po kroku min, rozpoczynamy proces, tworząc nową funkcję z następującymi wierszami kodu:
niech minHeap = funkcja ()// reszta kodu minimalnego będzie obecna
Pierwszym krokiem jest utworzenie tablicy i ustawienie wartości na indeksie 0 Jak zero:
Niech heap = [null];
Wtedy stworzymy Wstaw funkcję Korzystanie z następujących wierszy kodu:
Ten.insert = funkcja (num)
sterta.push (num);
if (sterta.długość> 2)
letidx = sterta.Długość - 1;
while (sterta [idx] = 1)
[sterta [matematyka.podłoga (idx / 2)], sterta [idx]] = [
sterta [idx],
sterta [matematyka.podłoga (IDX / 2)],
];
if (matematyka.podłoga (idx / 2)> 1)
idx = matematyka.podłoga (IDX / 2);
w przeciwnym razie
przerwa;
;
W tym fragmencie kodu dzieją się następujące rzeczy:
- Nowy element num jest dodawany do ostatniego indeksu tablicy
- Jeśli długość tablicy jest większa niż 2 elementy, sprawdzamy nowy element za pomocą jego węzła nadrzędnego
- Jeśli element jest mniejszy niż jego węzeł nadrzędny, jest zastępowany węzłem nadrzędnym, w przeciwnym razie wywnioskowamy, że sterta we właściwej kolejności
- Jeśli element zostanie zastąpiony węzłem nadrzędnym w poprzednim etapie, ponownie porównujemy go z jego nowym nadrzędnym, dopóki nie wydedukujemy, że stos jest właściwy lub element staje się węzłem głównym
Następnym krokiem jest wdrożenie Usuń funkcję Z następującymi wierszami kodu:
Ten.remove = function ()Niech najmniejszy = sterta [1];
if (sterta.długość> 2)
sterta [1] = sterta [sterta.długość - 1];
sterta.splice (sterta.długość - 1);
if (sterta.długość == 3)
if (sterta [1]> sterta [2])
[sterta [1], sterta [2]] = [sterta [2], sterta [1]];
powrót najmniejszego;
leti = 1;
letleft = 2 * i;
letright = 2 * i + 1;
while (sterta [i]> = sterta [lewy] || sterta [i]> = sterta [prawy])
if (sterta [po lewej] < heap[right])
[sterta [i], sterta [lewy]] = [sterta [lewy], sterta [i]];
i = 2 * i;
w przeciwnym razie
[sterta [i], sterta [right]] = [sterta [right], sterta [i]];
i = 2 * i + 1;
po lewej = 2 * i;
Right = 2 * i + 1;
if (sterta [lewy] == Undefined || sterta [prawy] == Undefined)
przerwa;
elseif (sterta.długość == 2)
sterta.splice (1, 1);
w przeciwnym razie
powrót NULL;
powrót najmniejszego;
;
Następujące kroki odbywają się w powyższym fragmencie kodu:
- Usuwamy węzeł główny, ponieważ jest to najmniejszy węzeł sterty
- Jeśli sterta ma tylko dwa elementy, wówczas drugi element staje się węzłem głównym
- Jeśli sterta ma 3 elementy, wówczas najmniejszy z drugiego i 3. elementu staje się węzłem głównym
- Jeśli element ma więcej niż 3 elementy, ostatni element sterty staje się węzłem głównym
- Następnie ten nowy węzeł korzeniowy jest porównywany z węzłami dziecięcymi i jest zastępowany mniejszym węzłem i jest przeciwny nowym węzłom dziecięcym (do wymiany używamy Metoda niszczenia obiektów)
- Ten proces porównywania elementu z węzłami dziecięcymi jest powtarzany, aż osiągnie punkt, w którym jest on mniejszy niż oba węzły dziecięce lub staje się ostatnim węzłem w tablicy.
Następnym krokiem jest utworzenie funkcji, która wyświetli nam tablicę sterty do konsoli, robimy to za pomocą następujących wierszy kodu:
Ten.show = function ()konsola.log (sterta);
;
Pełny fragment kodu wdrażania struktury danych min-heap jest:
letMinHeap = function ()Niech heap = [null];
Ten.insert = funkcja (num)
sterta.push (num);
if (sterta.długość> 2)
letidx = sterta.Długość - 1;
while (sterta [idx] = 1)
[sterta [matematyka.podłoga (idx / 2)], sterta [idx]] = [
sterta [idx],
sterta [matematyka.podłoga (IDX / 2)],
];
if (matematyka.podłoga (idx / 2)> 1)
idx = matematyka.podłoga (IDX / 2);
w przeciwnym razie
przerwa;
;
Ten.remove = function ()
Niech najmniejszy = sterta [1];
if (sterta.długość> 2)
sterta [1] = sterta [sterta.długość - 1];
sterta.splice (sterta.długość - 1);
if (sterta.długość == 3)
if (sterta [1]> sterta [2])
[sterta [1], sterta [2]] = [sterta [2], sterta [1]];
powrót najmniejszego;
leti = 1;
Niech lewy = 2 * i;
Niech w prawo = 2 * i + 1;
while (sterta [i]> = sterta [lewy] || sterta [i]> = sterta [prawy])
if (sterta [po lewej] < heap[right])
[sterta [i], sterta [lewy]] = [sterta [lewy], sterta [i]];
i = 2 * i;
w przeciwnym razie
[sterta [i], sterta [right]] = [sterta [right], sterta [i]];
i = 2 * i + 1;
po lewej = 2 * i;
Right = 2 * i + 1;
if (sterta [lewy] == Undefined || sterta [prawy] == Undefined)
przerwa;
elseif (sterta.długość == 2)
sterta.splice (1, 1);
w przeciwnym razie
ReturnNull;
powrót najmniejszego;
;
Ten.show = function ()
konsola.log (sterta);
;
;
Musimy teraz utworzyć nową minętową funkcję MinHeap, którą właśnie stworzyliśmy. Aby to zrobić, tworzymy nową zmienną i mapujemy ją na minheap za pomocą następujących wierszy kodu:
var newMinHeap = new MinHeap ();Następnie dodajmy wartości do sterty za pomocą następujących wierszy kodu:
Newminheap.wstaw (34);Newminheap.wstaw (61);
Newminheap.wstaw (138);
Newminheap.wstaw (82);
Newminheap.wstaw (27);
Newminheap.wstaw (35);
Teraz nazywamy pokazywać funkcja wyświetlania tablicy sterty na konsoli:
Newminheap.pokazywać();Otrzymujemy następujący wynik na naszej konsoli:
Jak widać, pierwszym elementem tablicy jest zero. Reszta węzłów nie jest większa niż ich węzły dziecięce. Na przykład, jeśli weźmiemy węzeł z wartością 35. Lewe i prawe dziecko są jak:
Możesz wyraźnie zobaczyć, rodzic (35) jest mniejsze niż lewe dziecko (82) i prawe dziecko (61). Podobnie każdy węzeł nadrzędny jest mniejszy niż jego węzeł dziecięcy, dlatego możemy wywnioskować, że nasz kod działa idealnie
Podobnie, po prostu zmieniając warunek porównywania, ponieważ bycie węzłem nadrzędnym jest mniejszy niż dziecko z węzłem nadrzędnym, który jest większy niż węzeł dziecięcy, możemy zaimplementować Max-heap Korzystanie z następujących wierszy kodu:
letmaxHeap = function ()Niech heap = [null];
Ten.insert = funkcja (num)
sterta.push (num);
if (sterta.długość> 2)
letidx = sterta.Długość - 1;
while (sterta [idx]> sterta [matematyka.podłoga (idx / 2)])
if (idx> = 1)
[sterta [matematyka.podłoga (idx / 2)], sterta [idx]] = [
sterta [idx],
sterta [matematyka.podłoga (IDX / 2)],
];
if (matematyka.podłoga (idx / 2)> 1)
idx = matematyka.podłoga (IDX / 2);
w przeciwnym razie
przerwa;
;
Ten.remove = function ()
Niech najmniejszy = sterta [1];
if (sterta.długość> 2)
sterta [1] = sterta [sterta.długość - 1];
sterta.splice (sterta.długość - 1);
if (sterta.długość == 3)
if (sterta [1] < heap[2])
[sterta [1], sterta [2]] = [sterta [2], sterta [1]];
powrót najmniejszego;
leti = 1;
Niech lewy = 2 * i;
Niech w prawo = 2 * i + 1;
While (sterta [i] <= heap[left] || heap[i] heap[right])
[sterta [i], sterta [lewy]] = [sterta [lewy], sterta [i]];
i = 2 * i;
w przeciwnym razie
[sterta [i], sterta [right]] = [sterta [right], sterta [i]];
i = 2 * i + 1;
po lewej = 2 * i;
Right = 2 * i + 1;
if (sterta [lewy] == Undefined || sterta [prawy] == Undefined)
przerwa;
elseif (sterta.długość == 2)
sterta.splice (1, 1);
w przeciwnym razie
ReturnNull;
powrót najmniejszego;
;
Ten.show = function ()
konsola.log (sterta);
;
;
To wszystko, z powodzeniem wdrożyłeś habetki binarne w JavaScript
Wniosek
Sterty binarne są wdrożeniem ciemieniowym drzewa binarnego o stanie posiadania najbardziej dwa węzły dziecięce dla każdego węzła nadrzędnego i pełna struktura drzewa binarnego. Co oznacza, że poziomy drzewa zostaną wypełnione od lewej lub lewej dziecka, a następnie prawego dziecka.
Sterty binarne są częścią zaawansowanych struktur danych i istnieją dwa rodzaje drzewa binarnego: jeden z nich nazywa się Min Kabel, podczas gdy drugi nazywa się maksymalną stertą. W minimalnej grupie węzły macierzysty mają mniejsze wartości niż ich węzły dziecięce, a wartości węzłów rodzeństwa nie mają znaczenia.
Podobnie, w maksymalnym heapie wartości węzła nadrzędnego są zawsze większe niż ich węzeł dziecięcy, a wartości węzłów rodzeństwa nie mają znaczenia. W tym poście dowiedzieliśmy się o heaps i ich wdrożeniu w waniliowym JavaScript, a na koniec przetestowaliśmy naszą implementację.