binary_heap.js

{
  class BinaryHeap {


  constructor() {
    this.data = []
  }

  insert(element) {
    this.data.push(element)
    let position = this.data.length - 1
    if (position === 0) {
      return
    }
    let parentPos = this._getParentPos(position)
    while(this.shouldSwap(position, parentPos)) {
      this._swap(position, parentPos)
      position = parentPos
      parentPos = this._getParentPos(position)
    }
  }

  remove(element) {
    let pos = this.data.findIndex(element)
    if (pos === -1) {
      return
    }
    // replace with the last
    this.data[pos] = this.data.pop()

    // todo, compare with children, swap if needed (bubble down)
    // minHeap: swap with the smallest child
    // maxHeap: swap with the largest child
  }

  shouldSwap(pos, parentPos) {
    if ('max Heap') {
      return this.data[pos] > this.data[parentPos]
    } else { // min heap
      return this.data[pos] < this.data[parentPos]
    }
  }

  _getParentPos(i) {
    return ((i + 1) / 2 | 0) - 1
  }

  _getFirstChildPos(i) {
    return i * 2 + 1
  }

  _swap(i, j) {
    let temp = this.data[i]
    this.data[i] = this.data[j]
    this.data[j] = temp
  }

  head() {
    return this.data[0]
  }

  clear() {
    this.data.length = 0
  }
}

// tests
let maxHeap = new BinaryHeap
maxHeap.insert(1)
maxHeap.insert(2)
maxHeap.insert(3)
maxHeap.insert(4)
maxHeap.insert(5)
maxHeap.insert(6)
maxHeap.insert(7)
console.log(maxHeap.data)   // [7, 4, 6, 1, 3, 2, 5]
console.log(maxHeap.head()) // 7

maxHeap.clear()
maxHeap.insert(7)
maxHeap.insert(6)
maxHeap.insert(5)
maxHeap.insert(4)
maxHeap.insert(3)
maxHeap.insert(2)
maxHeap.insert(1)
console.log(maxHeap.data)   // [7, 6, 5, 4, 3, 2, 1]
console.log(maxHeap.head()) // 7
}