今回は「「ある数でつくられた数列」を解くために：part5」の問題に挑戦！
前回も使ったヒープをJSのクラスで実装した部分を解説！

問題概要

3つの整数 A₁, A₂, A₃ が与えられる
N 個の整数 b₁, b₂, …, bₙ が順に与えられる
各 bᵢ について次を行う：
- bᵢ × A₁, bᵢ × A₂, bᵢ × A₃ を生成
- それらを優先度付きキュー（最小ヒープ）に追加
- その時点でヒープ内にある最小値を1つ取り出して出力

入力例：

出力例：

8
10
12

✅OK例：

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

const lines = [];

rl.on('line', line => {
    lines.push(line.trim());
});

rl.on('close', () => {
    const [A1, A2, A3] = lines[0].split(' ').map(Number);
    const N = Number(lines[1]);
    const b = lines.slice(2).map(Number);

    // 最小ヒープ（Min Heap）
    class MinHeap {
        constructor() {
            this.heap = [];
        }

        push(value) {
            this.heap.push(value);
            this._bubbleUp(this.heap.length - 1);
        }

        pop() {
            const min = this.heap[0];
            const last = this.heap.pop();

            if (this.heap.length > 0) {
                this.heap[0] = last;
                this._bubbleDown(0);
            }
            return min;
        }

        _bubbleUp(index) {
            while (index > 0) {
                const parent = Math.floor((index - 1) / 2);
                if (this.heap[parent] <= this.heap[index]) break;
                [this.heap[parent], this.heap[index]] =
                    [this.heap[index], this.heap[parent]];
                index = parent;
            }
        }

        _bubbleDown(index) {
            const length = this.heap.length;
            while (true) {
                let smallest = index;
                const left = index * 2 + 1;
                const right = index * 2 + 2;

                if (left < length && this.heap[left] < this.heap[smallest]) {
                    smallest = left;
                }
                if (right < length && this.heap[right] < this.heap[smallest]) {
                    smallest = right;
                }
                if (smallest === index) break;

                [this.heap[index], this.heap[smallest]] =
                    [this.heap[smallest], this.heap[index]];
                index = smallest;
            }
        }
    }

    const heap = new MinHeap();

    for (let i = 0; i < N; i++) {
        heap.push(BigInt(b[i]) * BigInt(A1));
        heap.push(BigInt(b[i]) * BigInt(A2));
        heap.push(BigInt(b[i]) * BigInt(A3));

        const current = heap.pop();
        console.log(current.toString());
    }
});

🔍コードの流れ

① 入力の受け取り

readline を使って標準入力をすべて lines 配列に格納
入力終了（close）後に処理開始

② 入力の解析

1行目：A1, A2, A3（掛ける3つの整数）
2行目：N（処理する個数）
3行目以降：b[0] ~ b[N-1]（元となる数列）

③ 最小ヒープ（MinHeap）クラス定義

目的：常に「最小値」を効率よく取り出す
内部は配列で管理
機能
- push：値を追加（上方向に調整）
- pop：最小値を取り出す（下方向に調整）
- _bubbleUp：親より小さければ上へ
- _bubbleDown：子より大きければ下へ

④ ヒープの準備

const heap = new MinHeap();
空の最小ヒープを用意

⑤ メイン処理（N 回ループ）

各 b[i] に対して：
- b[i] × A1
- b[i] × A2
- b[i] × A3
BigInt で計算
生成した 3 つの値をすべてヒープに追加

⑥ 最小値を1つ取り出す

heap.pop() を実行
現時点でヒープ内にある最小の値を取得
その値を即座に出力

⑦ 出力

各 b[i] を処理するたびに
1行ずつ最小値を表示
BigInt → toString() して出力

💡ヒープ: クラス解説

全体像（まずこれだけ押さえる）

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

  push(value) { ... }
  pop() { ... }

  _bubbleUp(index) { ... }
  _bubbleDown(index) { ... }
}

このクラスの目的：

「常に最小値を O(log N) で取り出せる箱」

constructor()

constructor() {
  // ヒープ本体（配列で管理）
  this.heap = [];
}

何をしている？

ヒープを配列で表現する
木構造を直接作らない

なぜ配列でいい？

ヒープは完全二分木なので
配列のインデックスで親子関係を計算できる。

ノード	インデックス
親	`(i - 1) / 2`
左の子	`2*i + 1`
右の子	`2*i + 2`

👉 木を作る必要がない＝速い・簡単

push(value)

push(value) {
  this.heap.push(value);
  this._bubbleUp(this.heap.length - 1);
}

役割

👉 新しい値をヒープに追加する

処理の流れ

末尾に追加（とりあえず）
ヒープ条件を壊している可能性がある
上に持ち上げて修復（bubbleUp）

なぜ末尾に入れる？

完全二分木を保つため
（途中に穴を開けると構造が壊れる）

_bubbleUp(index)

_bubbleUp(index) {
  while (index > 0) {
    const parent = Math.floor((index - 1) / 2);

    if (this.heap[parent] <= this.heap[index]) break;

    [this.heap[parent], this.heap[index]] =
      [this.heap[index], this.heap[parent]];

    index = parent;
  }
}

役割

👉 「子が親より小さい」状態を直す

具体的に何をしている？

今のノードの親を計算
親 ≤ 子なら OK → 終了
親 > 子なら交換
さらに上へチェック

例

heap = [2, 5, 3]
push(1)

[2, 5, 3, 1]
          ↑

bubbleUp 開始：

親 = 5 → 交換
[2, 1, 3, 5]

親 = 2 → 交換
[1, 2, 3, 5]

なぜ while？

一回の交換で終わるとは限らない
→ 根まで上がる可能性がある

pop()

pop() {
  const min = this.heap[0];
  const last = this.heap.pop();

  if (this.heap.length > 0) {
    this.heap[0] = last;
    this._bubbleDown(0);
  }

  return min;
}

役割

👉 最小値を取り出して削除する

処理の意味を分解

① 最小値を保存

const min = this.heap[0];

ヒープのルールで必ず最小

② 末尾を取り除く

const last = this.heap.pop();

⚠️ ここ重要：

Array の pop
再帰ではない
O(1)

③ 末尾を先頭に置く

this.heap[0] = last;

なぜ？

先頭を消すと穴が空く
末尾を持ってきて形を維持

④ 下に落として修復

this._bubbleDown(0);

先頭は大きすぎる可能性がある
子と比較して下へ落とす

_bubbleDown(index)

_bubbleDown(index) {
  const length = this.heap.length;

  while (true) {
    let smallest = index;

    const left = index * 2 + 1;
    const right = index * 2 + 2;

    if (left < length && this.heap[left] < this.heap[smallest]) {
      smallest = left;
    }
    if (right < length && this.heap[right] < this.heap[smallest]) {
      smallest = right;
    }

    if (smallest === index) break;

    [this.heap[index], this.heap[smallest]] =
      [this.heap[smallest], this.heap[index]];

    index = smallest;
  }
}

役割

👉 「親が子より大きい」状態を直す

具体的に何をしている？

左右の子のうち小さい方と比較
親 ≤ 子なら OK
親 > 子なら交換して下へ

例

[5, 2, 3, 7, 8]

親 5
子 2, 3 → 2 と交換

[2, 5, 3, 7, 8]

さらに下へ…

なぜ _ がついている？

_bubbleUp
_bubbleDown

意味

👉 「クラス内部用」メソッド (private)

外から直接使わない
慣習として _ をつける
※ # をつけて #bubbleUp と書くのがモダン

このクラスで守っているルール

常にこれを満たす：

heap[親] <= heap[子]

そのために：

操作	使う処理
push	bubbleUp
pop	bubbleDown

📝まとめ

ヒープ = 配列で表した完全二分木
最小値は必ず heap[0]
追加 → 上へ修正
削除 → 下へ修正
shift は使わない
pop は「消費する」ための操作