Cumuli binari in javascript
La proprietà heap
Questa proprietà può essere considerata un vincolo per la definizione di un albero, una determinata struttura che deve essere seguita durante la costruzione di un albero. Heap definisce una relazione tra i nodi genitori e i suoi nodi figlio, esistono due tipi di cumuli e quindi esistono due tipi di relazioni che possono esistere tra il nodo genitore e il nodo figlio:
- Heap max: il valore dei nodi genitori deve essere sempre maggiore o uguale ai nodi figlio
- Min-heap: il valore dei nodi genitori deve essere sempre più piccolo o uguale ai nodi figlio
Una rappresentazione del minimo è:
(Immagine di Wikipedia)
Come puoi vedere, nell'albero che i nodi genitori hanno valori più bassi rispetto ai nodi figlio
La rappresentazione AR del massimo è:
(Immagine di Wikipedia)
Puoi vedere che i nodi genitori hanno valori maggiori dei loro nodi figlio.
Rappresentazione dell'array
I cumuli in un linguaggio di programmazione sono rappresentati sotto forma di un array, un esempio dell'array di heap costruito dall'albero massimo di HAP sopra è:
var max-heap = [100,19,36,17,3,25,1,2,7];Quando si rappresenta un mucchio binario sotto forma di un array, si utilizza la seguente espressione per dedurre quanto segue:
- Figlio a sinistra = i * 2
- Bambino giusto = i * 2 + 1
- Genitore = i / 2
Dove "io" sta per l'indice dell'array. Parlando di indici, quando implementiamo le strutture heap usando un array, mettiamo a "nullo" Nel primo indice che è l'indice 0.
Rappresentazione visiva del funzionamento di un mucchio
Per una rappresentazione virtuale del funzionamento di un Min-Heap e di come vengono inseriti i valori nel mucchio, possiamo andare al visualizzatore del heap dell'Università di San Francisco facendo clic qui
Inserire i valori nel heap e noterai come un nuovo elemento viene inserito nel heap a causa dell'animazione:
Funzionante di heap
Un mucchio binario ha due funzioni principali:
- Il primo è aggiungere il nuovo elemento nella sua posizione appropriata
- La seconda funzione è rimuovere il valore della radice
Aggiunta di un nuovo elemento nel mucchio
Un nuovo elemento viene sempre aggiunto alla fine dell'array, quindi viene controllato contro il suo genitore e se va contro la proprietà heap, viene scambiato con il suo genitore. L'elemento viene controllato fino a quando non è stato confrontato con il nodo radice del heap (il nodo radice è il primo nodo del heap).
Rimozione di un elemento dal mucchio
Ogni volta che si desidera rimuovere o prendere un valore dal heap, prendi sempre il valore del nodo radicale. Ecco perché questo valore è il valore più piccolo se è un minimo e il valore più grande se si tratta di un max heap. Quando il nodo radice viene rimosso dall'heap, l'ultimo nodo dell'array prende il suo posto, quindi viene confrontato con i suoi nodi figlio per abbinare la condizione del mucchio. Se non corrisponde alla condizione, viene sostituito con il suo nodo figlio e quindi controllato con ulteriori nodi figlio. Un modo molto migliore per spiegare questo è usare lo spettatore heap dal vivo come mostrato di seguito:
È possibile osservare il processo di rimozione osservando la gif sopra.
Implementazione del cumulo binario in JavaScript
Implementeremo il Min-Heap passo dopo passo, iniziamo il processo creando una nuova funzione con le seguenti righe di codice:
let minHeap = function ()// Il resto del codice min-heap sarà presente
Il primo passo è creare un array e impostare il valore su indice 0 COME nullo:
let heap = [null];
Quindi creeremo il Inserire la funzione Utilizzando le seguenti righe di codice:
Questo.insert = function (num)
mucchio.push (num);
Se (heap.lunghezza> 2)
letidx = heap.lunghezza - 1;
while (heap [idx] = 1)
[heap [matematica.Floor (idx / 2)], heap [idx]] = [
heap [idx],
heap [matematica.pavimento (idx / 2)],
];
Se (matematica.Floor (idx / 2)> 1)
idx = matematica.pavimento (idx / 2);
altro
rottura;
;
Le seguenti cose stanno accadendo in questo frammento di codice:
- Un nuovo elemento Num viene aggiunto all'ultimo indice dell'array
- Se la lunghezza dell'array è maggiore di 2 elementi, controlliamo il nuovo elemento con il suo nodo genitore
- Se l'elemento è più piccolo del suo nodo genitore, viene sostituito con il suo nodo genitore, altrimenti deduciamo che il mucchio in ordine corretto
- Se l'elemento viene sostituito con il suo nodo genitore nel passaggio precedente, allora lo confrontiamo di nuovo con il suo nuovo genitore fino a quando non deduciamo che l'HEAP è in ordine corretto o che l'elemento diventa il nodo radice
Il prossimo passo è implementare il Rimuovere la funzione Con le seguenti righe di codice:
Questo.rimozione = function ()let più piccolo = heap [1];
Se (heap.lunghezza> 2)
heap [1] = heap [heap.lunghezza - 1];
mucchio.giunzione (heap.lunghezza - 1);
Se (heap.lunghezza == 3)
if (heap [1]> heap [2])
[heap [1], heap [2]] = [heap [2], heap [1]];
restituire il più piccolo;
leti = 1;
letleft = 2 * i;
LetRight = 2 * i + 1;
while (heap [i]> = heap [a sinistra] || heap [i]> = heap [a destra])
if (heap [a sinistra] < heap[right])
[heap [i], heap [a sinistra]] = [heap [a sinistra], heap [i]];
i = 2 * i;
altro
[heap [i], heap [diritto]] = [heap [destra], heap [i]];
i = 2 * i + 1;
a sinistra = 2 * i;
a destra = 2 * i + 1;
if (heap [a sinistra] == undefined || heap [a destra] == undefined)
rottura;
elseif (heap.lunghezza == 2)
mucchio.giunzione (1, 1);
altro
restituire null;
restituire il più piccolo;
;
I seguenti passaggi si stanno verificando nello snippet di codice sopra:
- Rimuoviamo il nodo radice in quanto è il nodo più piccolo del heap
- Se il heap ha solo due elementi, allora il 2 ° elemento diventa il nodo radice
- Se il heap ha 3 elementi, allora il più piccolo fuori dal 2 ° e 3 ° elemento diventa il nodo radice
- Se l'elemento ha più di 3 elementi, allora l'ultimo elemento del heap diventa il nodo radice
- Quindi questo nuovo nodo radicale viene confrontato con i suoi nodi figlio e viene sostituito con il nodo più piccolo ed è contro rispetto ai nuovi nodi figlio (per la sostituzione stiamo usando il Metodo di distruzione dell'oggetto)
- Questo processo di confronto dell'elemento con i nodi figlio viene ripetuto fino a raggiungere un punto in cui è più piccolo di entrambi i nodi figlio o diventa l'ultimo nodo nell'array.
Il prossimo passo è creare una funzione che ci visualizzerà l'array heap sulla console, lo facciamo utilizzando le seguenti righe di codice:
Questo.show = function ()console.log (heap);
;
Lo snippet completo del codice dell'implementazione della struttura dei dati Min-Heap è:
letMinHeap = function ()let heap = [null];
Questo.insert = function (num)
mucchio.push (num);
Se (heap.lunghezza> 2)
letidx = heap.lunghezza - 1;
while (heap [idx] = 1)
[heap [matematica.Floor (idx / 2)], heap [idx]] = [
heap [idx],
heap [matematica.pavimento (idx / 2)],
];
Se (matematica.Floor (idx / 2)> 1)
idx = matematica.pavimento (idx / 2);
altro
rottura;
;
Questo.rimozione = function ()
let più piccolo = heap [1];
Se (heap.lunghezza> 2)
heap [1] = heap [heap.lunghezza - 1];
mucchio.giunzione (heap.lunghezza - 1);
Se (heap.lunghezza == 3)
if (heap [1]> heap [2])
[heap [1], heap [2]] = [heap [2], heap [1]];
restituire il più piccolo;
leti = 1;
Lasciati a sinistra = 2 * i;
Lascia destra = 2 * i + 1;
while (heap [i]> = heap [a sinistra] || heap [i]> = heap [a destra])
if (heap [a sinistra] < heap[right])
[heap [i], heap [a sinistra]] = [heap [a sinistra], heap [i]];
i = 2 * i;
altro
[heap [i], heap [diritto]] = [heap [destra], heap [i]];
i = 2 * i + 1;
a sinistra = 2 * i;
a destra = 2 * i + 1;
if (heap [a sinistra] == undefined || heap [a destra] == undefined)
rottura;
elseif (heap.lunghezza == 2)
mucchio.giunzione (1, 1);
altro
returnnull;
restituire il più piccolo;
;
Questo.show = function ()
console.log (heap);
;
;
Quello che dobbiamo fare ora è creare un nuovo Min Heap usando la funzione MinHeap che abbiamo appena creato e quindi aggiungere elementi ad esso usando l'inserto e visualizzare il mucchio. Per fare ciò, realizziamo una nuova variabile e mappiamola su Minheap usando le seguenti righe di codice:
var newminHeap = new MinHeap ();Successivamente, aggiungiamo i valori all'heap usando le seguenti righe di codice:
Newminheap.inserire (34);Newminheap.inserire (61);
Newminheap.inserire (138);
Newminheap.inserire (82);
Newminheap.inserire (27);
Newminheap.inserire (35);
Ora chiamiamo il spettacolo funzione per visualizzare l'array heap sulla console:
Newminheap.spettacolo();Otteniamo il seguente risultato sulla nostra console:
Come puoi vedere, il primo elemento dell'array è nullo. Il resto dei nodi non è più grande dei nodi figlio. Ad esempio, se prendiamo il nodo con il valore 35. Il bambino sinistro e destro è come:
Puoi vedere chiaramente, il Il genitore (35) è più piccolo del bambino sinistro (82) e anche il suo bambino destro (61). Allo stesso modo, ogni nodo genitore è più piccolo del suo nodo figlio, quindi possiamo dedurre che il nostro codice funziona perfettamente
Allo stesso modo, modificando semplicemente la condizione per confrontare per essere il nodo genitore più piccolo del figlio con il nodo genitore più grande del nodo figlio possiamo implementare il Max-heap Utilizzando le seguenti righe di codice:
LetMaxHeap = function ()let heap = [null];
Questo.insert = function (num)
mucchio.push (num);
Se (heap.lunghezza> 2)
letidx = heap.lunghezza - 1;
while (heap [idx]> heap [matematica.pavimenti (idx / 2)])
if (idx> = 1)
[heap [matematica.Floor (idx / 2)], heap [idx]] = [
heap [idx],
heap [matematica.pavimento (idx / 2)],
];
Se (matematica.Floor (idx / 2)> 1)
idx = matematica.pavimento (idx / 2);
altro
rottura;
;
Questo.rimozione = function ()
let più piccolo = heap [1];
Se (heap.lunghezza> 2)
heap [1] = heap [heap.lunghezza - 1];
mucchio.giunzione (heap.lunghezza - 1);
Se (heap.lunghezza == 3)
if (heap [1] < heap[2])
[heap [1], heap [2]] = [heap [2], heap [1]];
restituire il più piccolo;
leti = 1;
Lasciati a sinistra = 2 * i;
Lascia destra = 2 * i + 1;
while (heap [i] <= heap[left] || heap[i] heap[right])
[heap [i], heap [a sinistra]] = [heap [a sinistra], heap [i]];
i = 2 * i;
altro
[heap [i], heap [diritto]] = [heap [destra], heap [i]];
i = 2 * i + 1;
a sinistra = 2 * i;
a destra = 2 * i + 1;
if (heap [a sinistra] == undefined || heap [a destra] == undefined)
rottura;
elseif (heap.lunghezza == 2)
mucchio.giunzione (1, 1);
altro
returnnull;
restituire il più piccolo;
;
Questo.show = function ()
console.log (heap);
;
;
Questo è tutto, hai implementato con successo un cumulo binario in JavaScript
Conclusione
I cumuli binari sono l'implementazione parietale di un albero binario con la condizione di avere al massimo Due nodi figlio per ciascun nodo genitore e la struttura completa dell'albero binario. Significa che i livelli dell'albero saranno riempiti dal lato sinistro o dal bambino sinistro e quindi dal bambino destro.
I cumuli binari fanno parte di strutture di dati avanzate e ci sono due tipi di albero binario: uno di essi è chiamato mucchio di min mentre l'altro è chiamato massimo massimo. Nel Min-Heap, i nodi genitori hanno valori più piccoli dei loro nodi figlio e i valori dei nodi tra fratelli non contano.
Allo stesso modo, in Max-heap, i valori del nodo genitore sono sempre maggiori del loro nodo figlio e i valori dei nodi tra fratelli non contano. In questo post, abbiamo appreso i cumuli e la loro implementazione in Vanilla Javascript e alla fine abbiamo testato la nostra implementazione.