DEV Community

1

二分ヒープの解説

参考のため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)
  }
}


Image of Timescale

🚀 pgai Vectorizer: SQLAlchemy and LiteLLM Make Vector Search Simple

We built pgai Vectorizer to simplify embedding management for AI applications—without needing a separate database or complex infrastructure. Since launch, developers have created over 3,000 vectorizers on Timescale Cloud, with many more self-hosted.

Read more →

Top comments (0)

Sentry image

See why 4M developers consider Sentry, “not bad.”

Fixing code doesn’t have to be the worst part of your day. Learn how Sentry can help.

Learn more