Implementando Heaps com NodeJS e Javascript

A Teoria da Coisa

Vamos lá, Heaps são árvores (trees), o que acontece aqui é que os Heads tem uma estrutura de certa forma pré-definida, já vamos ver o que é essa estrutura que um Heap segue. Árvores do tipo Heap servem na maioria dos casos pra gerenciar conjuntos de dados que precisam ter algum tipo de prioridade e também pra implementação de algoritmos de ordenação.

Um heap é uma árvore igual falei ali em cima, e segue a estrutura de árvore binária, lembra o que é isso? Se não lembra volta ali na implementação de árvores...(brincadeira) em resumo as árvores binárias são aquelas que todos os elementos menores que o primeiro nó da árvore vão pra um lado, e todos os maiores vão para outro lado, tem uns detalhes mas vamos ver isso depois.

Aqui nos Heaps, seguimos a mesma linha, onde o nó principal, ou a raiz, é o maior ou o menor valor com base nos outros valores da árvore, com base nisso temos dois nomes conhecidos para os Heaps, o max-heap (a raiz é o maior) e o min-heap (a raiz é o menor). Essas definições ajudam nas operações de inserção e remoção, mantendo sempre o maior ou o menor elemento na raiz (dependendo o que queremos), ou seja, o acesso ao elemento "mais importante" seria sempre no primeiro nó.

Mão na Massa

Bora fazer um min-heap, ou seja, onde o menor valor sempre vai estar na raiz...Pra fazer isso, vamos criar uma estrutura parecida com de uma árvore, mas aqui começa a complicar um pouco, porque pra ajudar, a gente pode usar um array, em vez de objetos igual na árvore, mas dá pra fazer seguindo a estrutura de árvore que vimos antes, só vai precisar de umas contas pra achar os índices dos filhos e dos pais, enfim, podemos deixar pra um próximo, vamos lá!

Agora a Prática

Agora abre aí o seu VSCode ou sua IDE favorita e vamos lá, crie um arquivo chamado heaps.js e cola o código abaixo:

class MinHeap {
  constructor() {
    this.heap = []
  }

  getParentIndex(i) {
    return Math.floor((i - 1) / 2)
  }
  getLeftChildIndex(i) {
    return 2 * i + 1
  }
  getRightChildIndex(i) {
    return 2 * i + 2
  }

  insert(key) {
    this.heap.push(key)
    this.heapifyUp()
  }
}

Explicando:

• MinHeap é a classe que criamos que vai dar vida ao Heap
• No constructor a gente inicializa o array heap que vai ser o nosso Heap de fato (onde vamos guardar os valores)
• getParentIndex, getLeftChildIndex e getRightChildIndex são funções auxiliares que vão nos ajudar a achar os índices dos pais e dos filhos de um nó
• insert é a função que vai inserir um valor no Heap

Só isso ainda não conseguimos ver toda a mágica do Heap, a gente precisa colocar mais algumas funções pra fazer a mágica acontecer, então depois do insert vamos colocar mais algumas funções, vou colocar uma por uma e explicar o que cada uma vai fazer.

O heapifyUp é a função que vai ajustar o Heap pra cima, ou seja, quando a gente inserir algum valor, ele vai subir na árvore até achar o lugar certo dele, então cola o código abaixo depois do insert:

  heapifyUp() {
    let index = this.heap.length - 1
    while (index !== 0 && this.heap[this.getParentIndex(index)] > this.heap[index]) {
      ;[this.heap[this.getParentIndex(index)], this.heap[index]] = [
        this.heap[index],
        this.heap[this.getParentIndex(index)],
      ]
      index = this.getParentIndex(index)
    }
  }

O heapifyDown é a função que vai ajustar o Heap pra baixo, ou seja, quando a gente remover algum valor, todos os outros elementos vão "andar uma casa" ou seja, descer na árvore até achar o lugar certo, então cola o código abaixo depois do heapifyUp:

  heapifyDown() {
    let index = 0
    while (this.getLeftChildIndex(index) < this.heap.length) {
      let smallerChildIndex = this.getLeftChildIndex(index)
      if (
        this.getRightChildIndex(index) < this.heap.length &&
        this.heap[this.getRightChildIndex(index)] < this.heap[smallerChildIndex]
      ) {
        smallerChildIndex = this.getRightChildIndex(index)
      }
      if (this.heap[index] < this.heap[smallerChildIndex]) break
      ;[this.heap[index], this.heap[smallerChildIndex]] = [
        this.heap[smallerChildIndex],
        this.heap[index],
      ]
      index = smallerChildIndex
    }
  }

O extractMin é a função que vai remover o menor valor do Heap, ou seja, o valor que está na raiz, e depois vai ajustar o Heap pra baixo, ou seja, andar uma casa com os outros valores até tudo ficar no lugar certo e garantir que o valor na raiz seja ainda o menor valor, então coloca o código abaixo depois do heapifyDown:

  extractMin() {
    if (!this.heap.length) return null
    if (this.heap.length === 1) return this.heap.pop()

    const min = this.heap[0]
    this.heap[0] = this.heap.pop()
    this.heapifyDown()
    return min
  }

TA QUASE ACABANDO, PROMETO!

Com tudo isso feito, vamos botar uns console.log raiz, criar uns elementos e ver como o Heap vai se comportar e ver se tá tudo funcionando como a gente espera, bora, cola o código abaixo no seu arquivo heaps.js depois da classe MinHeap:

const minHeap = new MinHeap()

minHeap.insert(10)
console.log(`minHeap insert 10:`, { heap: minHeap.heap })

minHeap.insert(5)
console.log(`minHeap insert 5:`, { heap: minHeap.heap })

minHeap.insert(15)
console.log(`minHeap insert 15:`, { heap: minHeap.heap })

minHeap.insert(20)
console.log(`minHeap insert 20:`, { heap: minHeap.heap })

minHeap.insert(30)
console.log(`minHeap insert 30:`, { heap: minHeap.heap })

minHeap.insert(2)
console.log(`minHeap insert 2:`, { heap: minHeap.heap })

Explicando:

• A gente cria um novo Heap com const minHeap = new MinHeap()
• Depois a gente insere alguns valores no Heap com insert

Agora a última parte pra gente ver se ta tudo certinho, depois dos inserts acima, coloca isso aqui:

console.log(`1 extraction of current min value:`, {
  currentMinValue: minHeap.extractMin(),
  heap: minHeap.heap,
})

console.log(`2 extraction of current min value:`, {
  currentMinValue: minHeap.extractMin(),
  heap: minHeap.heap,
})

console.log(`3 extraction of current min value:`, {
  currentMinValue: minHeap.extractMin(),
  heap: minHeap.heap,
})

Explicando:

• Estamos fazendo 3 logs, já com um objeto que trás o menor valor e como o Heap ta depois da remoção
• A gente chama a função extractMin pra remover o menor valor do Heap (que esperamos que seja o valor que ta na raiz)
• Depois a gente chama de novo a função extractMin pra remover o menor valor atual do Heap (que esperamos de novo que seja o valor que ta na raiz)

Fazemos isso 3 vezes pra ver se ta tudo certinho, se tudo deu certo, você deve ver algo parecido com isso no seu terminal:

node ./heaps.js
minHeap insert 10: { heap: [ 10 ] }
minHeap insert 5: { heap: [ 5, 10 ] }
minHeap insert 15: { heap: [ 5, 10, 15 ] }
minHeap insert 20: { heap: [ 5, 10, 15, 20 ] }
minHeap insert 30: { heap: [ 5, 10, 15, 20, 30 ] }
minHeap insert 2: { heap: [ 2, 10, 5, 20, 30, 15 ] }
1 extraction of current min value: { currentMinValue: 2, heap: [ 5, 10, 15, 20, 30 ] }
2 extraction of current min value: { currentMinValue: 5, heap: [ 10, 20, 15, 30 ] }
3 extraction of current min value: { currentMinValue: 10, heap: [ 15, 20, 30 ] }

Me avisa e coloca um comentário aqui se você descobrir porque quando incluimos o 2 ele ficou na posição certa como raiz (antes do 10), mas porque o 10 não ficou depois do 5, e sim depois do 2?

Vou parar o código por aqui e deixar pra você testar, o que acha de tentar aplicar esse conceito, mas na estrutura de árvore que fizemos uns posts atrás? Será que dá pra fazer? Se fizer, me avisa, quero ver!

Aonde Você Pode Usar/Ver

Gerenciamento de Filas de Prioridade

Heaps são ideais para implementar filas de prioridade, onde elementos são processados com base na prioridade em vez de na ordem de chegada. Isso é essencial em sistemas operacionais, simulações, algoritmos de agendamento, enfim, variaas aplicações.

Algoritmos de Ordenação e Busca

Heaps facilitam a implementação de algoritmos de ordenação eficientes, como o heapsort, e são usados também em algoritmos de busca "menor caminho" que vamos ver mais pra frente, que basicamente são algoritmos que buscam elementos em grafos tentando realizar o menor caminho possível entre os elementos dos grafos, como o Dijkstra.

Dicas

• Utilizamos uma lista para manter a simplicidade e aproveitar o acesso direto dos elementos pais e filhos, mas você pode implementar um heap com uma árvore binária se preferir.
• Quando fazemos o heapify, temos que garantir que o heap vai manter sua estrutura depois de cada insert ou de cada remove, pra não quebrar o conceito que queremos de sempre ter o menor valor (ou o maior se for o caso) na raiz do nosso Heap.
• Teste a implementação do Heap com mais dados e diferentes tipos de dados (por exemplo um Heap que tenha objetos e cada objeto tem uma prioridade/nota, etc) pra garantir a eficiência em cenários mais complexos e próximos de projetos reais.

Considerações do Jon

Igual as Hash Tables, geralmente já temos alguma lib ou função/estrutura que já tem implementação de Heaps, então não é algo que a gente vai implementar do zero sempre, mas caso você precise para algo especifico ou mesmo pra aprender já temos uma base pra começar, e evoluir em cima disso vai ser mais fácil e ao mesmo tempo um bom desafio que vai fazer você aprender muito (eu também aprendo e relembro muita coisa quando estou fazendo esses posts).

Lembrando que é sempre bom ter esses conceitos na manga, as vezes você pode resolver um problema de performance só trocando a estrutura ou o tipo de implementação que você ta usando no seu projeto.

E Você?!

Já criou/utilizou algo parecido nos seus projetos ou no seu trampo? Se quiser, comenta aqui, se já fez, experiências, desafios, dicas, etc!!

Vamos explorar esses conceitos juntos, ah e se viu algum bug, erro, melhoria, também comenta aí!