Montes binários em javascript
A propriedade Heap
Esta propriedade pode ser considerada uma restrição para definir uma árvore, uma certa estrutura que deve ser seguida ao construir uma árvore. O HEAP define uma relação entre os nós pais e seus nós filhos, existem dois tipos de pilhas e, portanto, existem dois tipos de relacionamento que podem existir entre o nó pai e o nó filho:
- Max-heap: O valor dos nós pais deve sempre ser maior ou igual aos nós filhos
- Min-Heap: O valor dos nós pais deve sempre ser menor ou igual aos nós filhos
Uma representação do min-heap é:
(Imagem da Wikipedia)
Como você pode ver, na árvore que os nós pais têm valores mais baixos do que seus nós filhos
Representação do AR do Max-Heap é:
(Imagem da Wikipedia)
Você pode ver que os nós pais têm valores maiores que os nós filhos deles.
Representação da matriz
Os montes em uma linguagem de programação são representados na forma de uma matriz, um exemplo da matriz de heap construída a partir da árvore max-heap acima é:
var max-heap = [100,19,36,17,3,25,1,2,7];Ao representar uma pilha binária na forma de uma matriz, você usa a seguinte expressão para deduzir o seguinte:
- Filho esquerdo = i * 2
- Criança direita = i * 2 + 1
- Pai = i / 2
Onde "eu" significa o índice da matriz. Falando sobre índices, quando implementamos estruturas de heap usando uma matriz, colocamos um "nulo" No primeiro índice, que é o índice 0.
Representação visual do trabalho de uma pilha
Para uma representação virtual do funcionamento de um min-heap e como os valores são inseridos na pilha, podemos ir ao visualizador de heap pela Universidade de São Francisco clicando aqui
Insira valores na pilha e você notará como um novo elemento é inserido na pilha devido à animação:
Trabalho de heap
Uma pilha binária tem duas funções principais:
- Primeiro é adicionar o novo elemento em sua posição apropriada
- A segunda função é remover o valor raiz
Adicionando um novo elemento na pilha
Um novo elemento é sempre adicionado no final da matriz e depois é verificado contra seus pais e, se for contra a propriedade Heap, será trocada com seus pais. O elemento é verificado até que tenha sido comparado com o nó raiz da pilha (o nó raiz é o primeiro nó da pilha).
Removendo um elemento da pilha
Sempre que você quiser remover ou buscar um valor da pilha, você sempre busca o valor do nó raiz. É por isso que esse valor é o menor valor se for um min-heap e o maior valor se for um max-heap. Quando o nó raiz é removido da pilha, o último nó da matriz toma seu lugar, então é comparado com seus nós filhos para combinar com a condição da pilha. Se não corresponder à condição, é substituído por seu nó filho e depois verificado com outros nós filhos. Uma maneira muito melhor de explicar isso é usando o visualizador de heap ao vivo, como mostrado abaixo:
Você pode observar o processo de remoção observando o GIF acima.
Implementando o monte binário em JavaScript
Vamos implementar o Min-Heap passo a passo, começamos o processo criando uma nova função com as seguintes linhas de código:
Seja MINNHEAP = function ()// O restante do código min-heap estará presente
O primeiro passo é criar uma matriz e definir o valor no índice 0 como nulo:
deixe heap = [nulo];
Então vamos criar o Inserir função Usando as seguintes linhas de código:
esse.insert = function (num)
pilha.push (num);
if (heap.comprimento> 2)
letidx = heap.comprimento - 1;
while (heap [idx] = 1)
[heap [matemática.piso (idx / 2)], heap [idx]] = [
Heap [IDX],
heap [matemática.piso (IDX / 2)],
];
if (matemática.piso (idx / 2)> 1)
idx = matemática.piso (idx / 2);
outro
quebrar;
;
As seguintes coisas estão acontecendo neste trecho de código:
- Um novo elemento num é adicionado no último índice da matriz
- Se o comprimento da matriz for maior que 2 elementos, verificamos o novo elemento com seu nó pai
- Se o elemento for menor que o nó pai, será substituído pelo nó pai, caso contrário, deduzimos que a pilha em ordem correta
- Se o elemento for substituído por seu nó pai na etapa anterior, então o comparamos novamente com seu novo pai até deduzir que Heap está em ordem correta ou o elemento se tornará o nó raiz
O próximo passo é implementar o Remova a função com as seguintes linhas de código:
esse.remover = function ()deixe menor = heap [1];
if (heap.comprimento> 2)
heap [1] = heap [heap.comprimento - 1];
pilha.emenda (heap.comprimento - 1);
if (heap.comprimento == 3)
if (heap [1]> heap [2])
[heap [1], heap [2]] = [heap [2], heap [1]];
retornar menor;
leti = 1;
letleft = 2 * i;
altura = 2 * i + 1;
while (heap [i]> = heap [esquerda] || heap [i]> = heap [direita])
if (heap [esquerda] < heap[right])
[heap [i], heap [esquerda]] = [heap [esquerda], heap [i]];
i = 2 * i;
outro
[heap [i], heap [direita]] = [heap [direita], heap [i]];
i = 2 * i + 1;
Esquerda = 2 * i;
direita = 2 * i + 1;
if (heap [esquerda] == indefinido || heap [direita] == indefinido)
quebrar;
elseif (heap.comprimento == 2)
pilha.emenda (1, 1);
outro
retornar nulo;
retornar menor;
;
As etapas a seguir estão acontecendo no trecho de código acima:
- Removemos o nó raiz, pois é o menor nó da pilha
- Se o heap tiver apenas dois elementos, o segundo elemento se tornará o nó raiz
- Se o heap tiver 3 elementos, o menor do 2º e 3º elemento se tornará o nó raiz
- Se o elemento tiver mais de 3 elementos, então o último elemento da pilha se tornará o nó raiz
- Em seguida, este novo nó raiz é comparado com seus nós filhos e é substituído pelo nó menor e é contra comparado com os novos nós filhos (para substituição, estamos usando o Método de destruição de objetos)
- Esse processo de comparação do elemento com os nós filhos é repetido até chegar a um ponto em que é menor do que os dois nós da criança ou se torna o último nó na matriz.
A próxima etapa é criar uma função que nos exibirá a matriz de heap no console, fazemos isso usando as seguintes linhas de código:
esse.show = function ()console.log (heap);
;
O trecho de código completo de implementar a estrutura de dados min-heap é:
letminhap = function ()deixe heap = [nulo];
esse.insert = function (num)
pilha.push (num);
if (heap.comprimento> 2)
letidx = heap.comprimento - 1;
while (heap [idx] = 1)
[heap [matemática.piso (idx / 2)], heap [idx]] = [
Heap [IDX],
heap [matemática.piso (IDX / 2)],
];
if (matemática.piso (idx / 2)> 1)
idx = matemática.piso (idx / 2);
outro
quebrar;
;
esse.remover = function ()
deixe menor = heap [1];
if (heap.comprimento> 2)
heap [1] = heap [heap.comprimento - 1];
pilha.emenda (heap.comprimento - 1);
if (heap.comprimento == 3)
if (heap [1]> heap [2])
[heap [1], heap [2]] = [heap [2], heap [1]];
retornar menor;
leti = 1;
Deixe para a esquerda = 2 * i;
deixe certo = 2 * i + 1;
while (heap [i]> = heap [esquerda] || heap [i]> = heap [direita])
if (heap [esquerda] < heap[right])
[heap [i], heap [esquerda]] = [heap [esquerda], heap [i]];
i = 2 * i;
outro
[heap [i], heap [direita]] = [heap [direita], heap [i]];
i = 2 * i + 1;
Esquerda = 2 * i;
direita = 2 * i + 1;
if (heap [esquerda] == indefinido || heap [direita] == indefinido)
quebrar;
elseif (heap.comprimento == 2)
pilha.emenda (1, 1);
outro
returnNull;
retornar menor;
;
esse.show = function ()
console.log (heap);
;
;
O que precisamos fazer agora é criar um novo min-heap usando a função MINHEAP que acabamos de criar e depois adicionar elementos a ele usando a inserção e exibir o heap. Para fazer isso, fabricamos uma nova variável e mapeamos no MINHEAP usando as seguintes linhas de código:
var newminhap = new MINHEAP ();Em seguida, vamos adicionar valores à pilha usando as seguintes linhas de código:
Newminhap.inserir (34);Newminhap.inserir (61);
Newminhap.inserir (138);
Newminhap.inserir (82);
Newminhap.inserir (27);
Newminhap.inserir (35);
Agora, chamamos o mostrar função para exibir a matriz de heap no console:
Newminhap.mostrar();Temos o seguinte resultado em nosso console:
Como você pode ver, o primeiro elemento da matriz é nulo. O resto dos nós não é maior do que os nós filhos. Por exemplo, se levarmos o nó com o valor 35. A criança esquerda e a direita são como:
Você pode ver claramente o pai (35) é menor que o filho esquerdo (82) e seu filho certo (61) também. Da mesma forma, todo nó dos pais é menor que seu nó filho, portanto, podemos deduzir que nosso código está funcionando perfeitamente
Da mesma forma, apenas mudando a condição para comparar por ser o nó pai sendo menor que a criança para o nó pai sendo maior que o nó infantil, podemos implementar o Max-heap Usando as seguintes linhas de código:
letmaxheap = function ()deixe heap = [nulo];
esse.insert = function (num)
pilha.push (num);
if (heap.comprimento> 2)
letidx = heap.comprimento - 1;
while (heap [idx]> heap [matemática.piso (idx / 2)])
if (idx> = 1)
[heap [matemática.piso (idx / 2)], heap [idx]] = [
Heap [IDX],
heap [matemática.piso (IDX / 2)],
];
if (matemática.piso (idx / 2)> 1)
idx = matemática.piso (idx / 2);
outro
quebrar;
;
esse.remover = function ()
deixe menor = heap [1];
if (heap.comprimento> 2)
heap [1] = heap [heap.comprimento - 1];
pilha.emenda (heap.comprimento - 1);
if (heap.comprimento == 3)
if (heap [1] < heap[2])
[heap [1], heap [2]] = [heap [2], heap [1]];
retornar menor;
leti = 1;
Deixe para a esquerda = 2 * i;
deixe certo = 2 * i + 1;
enquanto (heap [i] <= heap[left] || heap[i] heap[right])
[heap [i], heap [esquerda]] = [heap [esquerda], heap [i]];
i = 2 * i;
outro
[heap [i], heap [direita]] = [heap [direita], heap [i]];
i = 2 * i + 1;
Esquerda = 2 * i;
direita = 2 * i + 1;
if (heap [esquerda] == indefinido || heap [direita] == indefinido)
quebrar;
elseif (heap.comprimento == 2)
pilha.emenda (1, 1);
outro
returnNull;
retornar menor;
;
esse.show = function ()
console.log (heap);
;
;
É isso, você implementou com sucesso um monte binário em javascript
Conclusão
Montes binários são a implementação parietal de uma árvore binária com a condição de ter no máximo dois nós filhos para cada nó dos pais e a estrutura completa da árvore binária. O que significa que os níveis da árvore serão preenchidos do lado esquerdo ou do filho esquerdo e depois do filho direito.
Pilhas binárias fazem parte de estruturas de dados avançadas e existem dois tipos de árvore binária: um deles é chamado de Min Heap enquanto o outro é chamado de pilha máxima. No min-heap, os nós pais têm valores menores do que seus nós filhos e os valores dos nós do irmão não importa.
Da mesma forma, no max-heap, os valores do nó pai são sempre maiores que o nó filho e os valores dos nós irmãos não importam. Nesta postagem, aprendemos sobre HEAPs e sua implementação em JavaScript de baunilha e, no final, testamos nossa implementação.