二分ヒープの解説

参考のためDijkstraの際に使った最小ヒープのコード抜粋を下に貼ります。

const MinHeap = function (n) {
  this.a = [...Array(n).keys()].map(v => [v, Number.MAX_SAFE_INTEGER]) // [vertex, weight]
  this.pos = [...Array(n).keys()].map(v => v)
  this.size = n
}

MinHeap.prototype.extractMin = function () {
  const [v, w] = this.a[0]
  this.swap(0, this.size - 1)
  this.size--
  this.popDown(0)
  return [v, w]
}

MinHeap.prototype.swap = function (i, j) {
  const vi = this.a[i][0], vj = this.a[j][0];
  [this.a[i], this.a[j]] = [this.a[j], this.a[i]];
  [this.pos[vi], this.pos[vj]] = [this.pos[vj], this.pos[vi]]
}

MinHeap.prototype.decreaseKey = function (v, val) {
  const i = this.pos[v]
  this.a[i][1] = val
  this.popUp(i)
}

// vertexが含まれているか
MinHeap.prototype.contains = function (v) {
  return this.pos[v] < this.size
}

// 適切な位置まで上げる
MinHeap.prototype.popUp = function (i) {
  let pi = parent(i)
  while (i > 0 && this.a[i][1] < this.a[pi][1]) { // 親が子より大きかったら交換
    this.swap(i, pi)
    i = pi
    pi = parent(i)
  }
}

// 値を取得
MinHeap.prototype.val = function (v) {
  return this.a[this.pos[v]][1]
}

// 適切な位置まで下げる
MinHeap.prototype.popDown = function (i) {
  const val = this.a[i][1]
  let candidate = null // 子供のほうが小さかったら交換
  const ri = rightChild(i)
  const li = leftChild(i)
  if (ri < this.size) { // right child exist
    if (this.a[ri][1] < val) {
      candidate = ri
    }
  }
  if (li < this.size) {
    if (candidate == null) {
      if (this.a[li][1] < val) {
        candidate = li
      }
    } else {
      if (this.a[li][1] < this.a[ri][1]) {
        candidate = li
      }
    }
  }
  if (candidate != null) {
    this.swap(i, candidate)
    this.popDown(candidate)
  }
}