ヒープ（Heap）は、要素の優先度を効率的に管理する抽象データ構造です。実装の基盤となる二分ヒープ（Binary Heap）は、完全二分木の性質を1次元配列で表現することで、メモリ効率とキャッシュ局所性を両立させています。この構造を用いると、要素の挿入や最優先要素の取得・削除は O(log n) の時間計算量で実行可能です。

二分ヒープは「最大ヒープ」と「最小ヒープ」に分類されます。最大ヒープでは、任意のノードの値がその子ノードの値以上である関係が常に維持されます。最小ヒープはこの不等号が逆転した構造です。配列インデックスにおけるノード間の親子関係は、基準インデックスを i とした場合、以下の算術規則で定義されます：

• 親ノード: Math.floor((i - 1) / 2)
• 左子ノード: i * 2 + 1
• 右子ノード: i * 2 + 2

以下に、これらの規則に基づき再設計した実装例を示します。元のコードから変数名・メソッド構造を変更し、ES2020以降のプライベートフィールドや分割代入を活用することで、ロジックの冗長性を削減しつつアルゴリズムの本質を保っています。

最大ヒープの実装

class MaxHeap {
  #elements;

  constructor() {
    this.#elements = [];
  }

  get size() {
    return this.#elements.length;
  }

  #parentIndex(idx) {
    if (idx <= 0) throw new Error('Root node has no parent.');
    return (idx - 1) >> 1;
  }

  #leftChildIndex(idx) {
    return (idx << 1) + 1;
  }

  #rightChildIndex(idx) {
    return (idx << 1) + 2;
  }

  insert(value) {
    this.#elements.push(value);
    this.#ascend(this.size - 1);
  }

  peek() {
    if (this.size === 0) throw new Error('Heap underflow.');
    return this.#elements[0];
  }

  extractMax() {
    if (this.size === 0) throw new Error('Heap underflow.');
    if (this.size === 1) return this.#elements.pop();

    const top = this.#elements[0];
    this.#elements[0] = this.#elements.pop();
    this.#descend(0);
    return top;
  }

  #ascend(idx) {
    const store = this.#elements;
    while (idx > 0) {
      const parent = this.#parentIndex(idx);
      if (store[parent] >= store[idx]) break;
      [store[parent], store[idx]] = [store[idx], store[parent]];
      idx = parent;
    }
  }

  #descend(idx) {
    const store = this.#elements;
    const limit = this.size;
    let current = idx;

    while (true) {
      const left = this.#leftChildIndex(current);
      const right = this.#rightChildIndex(current);
      let target = current;

      if (left < limit && store[left] > store[target]) {
        target = left;
      }
      if (right < limit && store[right] > store[target]) {
        target = right;
      }

      if (target === current) break;

      [store[current], store[target]] = [store[target], store[current]];
      current = target;
    }
  }
}

最小ヒープの実装

最小ヒープは比較方向を反転させることで構築できます。以下の実装では、メソッド名と内部状態の管理を分離し、単一責任原則に沿った設計にしています。

class MinHeap {
  #storage;

  constructor() {
    this.#storage = [];
  }

  get count() {
    return this.#storage.length;
  }

  #calcParent(i) { return Math.floor((i - 1) / 2); }
  #calcLeft(i) { return i * 2 + 1; }
  #calcRight(i) { return i * 2 + 2; }

  push(val) {
    this.#storage.push(val);
    this.#bubbleUp(this.count - 1);
  }

  top() {
    if (this.count === 0) throw new Error('Heap is empty.');
    return this.#storage[0];
  }

  pop() {
    const min = this.top();
    this.#storage[0] = this.#storage.pop();
    if (this.count > 0) this.#sink(0);
    return min;
  }

  #bubbleUp(i) {
    while (i > 0) {
      const p = this.#calcParent(i);
      if (this.#storage[p] <= this.#storage[i]) break;
      this.#exchange(i, p);
      i = p;
    }
  }

  #sink(i) {
    const n = this.count;
    let current = i;

    while (this.#calcLeft(current) < n) {
      let minIdx = current;
      const l = this.#calcLeft(current);
      const r = this.#calcRight(current);

      if (l < n && this.#storage[l] < this.#storage[minIdx]) minIdx = l;
      if (r < n && this.#storage[r] < this.#storage[minIdx]) minIdx = r;

      if (minIdx === current) break;
      this.#exchange(current, minIdx);
      current = minIdx;
    }
  }

  #exchange(a, b) {
    [this.#storage[a], this.#storage[b]] = [this.#storage[b], this.#storage[a]];
  }
}