Implementando Heap com NodeJS e Javascript

Precisa sempre saber qual é o menor (ou maior) item sem varrer a lista inteira? Heap mantém esse elemento no topo em O(log n) por inserção/remoção — base de fila de prioridade e heapsort.

O que você vai aprender:

• Min-heap vs max-heap
• Representar heap em array (índices pai/filho)
• insert, heapify e extrair o mínimo
• Relação com árvore binária sem montar nós com ponteiros

Pré-requisitos: árvores (ep. 6) e hash tables (ep. 8).

Heap binário: min-heap em array

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ó com 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.

Edge cases: heapify após insert e dados arbitrários

Esquecer heapify depois de push no array quebra a propriedade do heap — o índice 0 deixa de ser o mínimo real.

"Tá Jon, heap só serve pra número?"

Não. Basta definir prioridade (campo priority ou comparador). O array guarda objetos; a comparação usa a regra que você passar.

TL;DR — Heap

Próximos passos

• Fila de prioridade (ep. 10): heap na API — Implementando Filas de Prioridade
• Ordenação (ep. 15): heapsort na prática — Ordenando arrays

Antes de fechar

Já usou fila de prioridade em job, alerta ou jogo? Comenta — e se o exemplo do insert(2) te fez pensar, manda sua versão do heapify.