BFE.devでのAI解答例 - JavaScript コーディング問題
24. JavaScriptでPriority Queueを実装する

解答例:

class PriorityQueue {
  constructor(compare) {
    this.heap = [];
    this.compare = compare;
  }

  add(element) {
    this.heap.push(element);
    this.bubbleUp(this.heap.length - 1);
  }

  poll() {
    if (this.size() === 0) {
      return null;
    }
    const head = this.heap[0];
    const tail = this.heap.pop();
    if (this.size() !== 0) {
      this.heap[0] = tail;
      this.bubbleDown(0);
    }
    return head;
  }

  peek() {
    if (this.size() === 0) {
      return null;
    }
    return this.heap[0];
  }

  size() {
    return this.heap.length;
  }

  // idxの要素が親よりも小さくなるまで親と交換する
  bubbleUp(idx) {
    while (idx > 0) {
      const parentIdx = Math.floor((idx + 1) / 2) - 1;
      if (this.compare(this.heap[idx], this.heap[parentIdx]) < 0) {
        const tmp = this.heap[parentIdx];
        this.heap[parentIdx] = this.heap[idx];
        this.heap[idx] = tmp;
      } else {
        break;
      }
      idx = parentIdx;
    }
  }

  // idxの要素が子よりも大きくなるまで子と交換する
  bubbleDown(idx) {
    while (true) {
      const leftChildIdx = 2 * idx + 1;
      const rightChildIdx = 2 * idx + 2;
      let minChildIdx = -1;
      if (leftChildIdx < this.size() && rightChildIdx < this.size()) {
        minChildIdx =
          this.compare(this.heap[leftChildIdx], this.heap[rightChildIdx]) < 0
            ? leftChildIdx
            : rightChildIdx;
      } else if (leftChildIdx < this.size()) {
        minChildIdx = leftChildIdx;
      } else if (rightChildIdx < this.size()) {
        minChildIdx = rightChildIdx;
      } else {
        break;
      }
      if (this.compare(this.heap[minChildIdx], this.heap[idx]) < 0) {
        const tmp = this.heap[minChildIdx];
        this.heap[minChildIdx] = this.heap[idx];
        this.heap[idx] = tmp;
        idx = minChildIdx;
      } else {
        break;
      }
    }
  }
}

この実装では、配列をヒープとして使っています。addメソッドでは、配列の末尾に要素を追加し、その要素を適切な位置までバブルアップします。pollメソッドでは、クエを取り出します。配列の先頭の要素を取得し、ヒープの最後の要素を先頭に移動し、末尾の要素を削除し、もともとの最初の要素を適切な位置にバブルアップします。peekメソッドは、先頭の要素を返すだけです。最後に、sizeメソッドは、配列の長さを返します。bubbleUpメソッドとbubbleDownメソッドは、ヒープの二分木内で適切な位置に要素を配置するための機能を提供します。