Implementando Heap com NodeJS e Javascript

Implementando Heap com NodeJS e Javascript | jonathanjuliani.dev

código

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()
  }
}

código

  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)
    }
  }

código

  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
    }
  }

código

  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
  }

código

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 })

código

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,
})

código

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 ] }

Operação	Complexidade típica
Ver mínimo/máximo	O(1) na raiz
Inserir	O(log n)
Remover raiz	O(log n)
Array	Pai `i`, filhos `2i+1`, `2i+2`

Vamos conversar

Implementando Heap com NodeJS e Javascript

Heap binário: min-heap em array

Mão na Massa

Agora a Prática

Aonde Você Pode Usar/Ver

Gerenciamento de Filas de Prioridade

Algoritmos de Ordenação e Busca

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

TL;DR — Heap

Próximos passos

Antes de fechar

Inscreva-se no Ledger da Engenharia

Heap binário: min-heap em array

Mão na Massa

Agora a Prática

Aonde Você Pode Usar/Ver

Gerenciamento de Filas de Prioridade

Algoritmos de Ordenação e Busca

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

TL;DR — Heap

Próximos passos

Antes de fechar

Inscreva-se no Ledger da Engenharia

Artigos relacionados