今回は paiza の「「ある数でつくられた数列」を解くために:part4」の問題に挑戦！
js にはヒープが標準で無いらしく、クラスで再現してみた！

問題概要

入力として
- 3つの素数 P1, P2, P3
- 自然数 k
  が与えられる
「数列」を次のルールで作る
- 初項は 1
- 1 に P1, P2, P3 を何回でも掛けてよい
- どの素数を使わなくてもよい
そうして作れるすべての数を
- 重複を除いて
- 小さい順に並べた数列
  と考える
その数列の k 番目に小さい数を出力する

入力例:

2 3 5 7

出力例:

✅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 [P1, P2, P3, k] = lines[0].split(' ').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(); // 配列（Array）の 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);

                // 親の方が小さければOK
                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();

    // 重複防止用セット
    const seen = new Set();

    // 数列の最初の要素は 1
    heap.push(1);
    seen.add(1);

    let current = 1;


    // k 回、最小値を取り出す
    for (let i = 0; i < k; i++) {
        // 現時点で一番小さい数
        current = heap.pop(); // インスタンスメソッド呼び出し → 最小値取得

        // current に 3つの素数を掛ける
        for (const p of [P1, P2, P3]) {
            const next = current * p;

            // まだ生成されていなければ追加
            if (!seen.has(next)) {
                seen.add(next);
                heap.push(next);
            }
        }
    }

    // k番目の数を出力
    console.log(current);
});

🔍コードの流れ

標準入力の準備
- readline を使って入力を1行ずつ lines 配列に保存する
- 入力が終わったら close イベントで処理開始
入力の読み取り
- 1行目から P1, P2, P3, k を取得
- 3つの素数と「何番目を求めるか」を決定
最小ヒープ（MinHeap）の定義
- 常に「一番小さい数」を取り出せるデータ構造
- push：値を追加
- pop：最小値を取り出す
- 内部で配列を使い、順序を保つ
初期化
- ヒープに 1 を追加（数列の最初の要素）
- Set に 1 を登録（重複防止用）
- current を用意
k 回ループ
- ヒープから最小値を取り出す → current
- current に対して
  - P1, P2, P3 を掛ける
- まだ出ていない値だけを
  - Set に登録
  - ヒープに追加
結果の出力
- k 回目に取り出した current を出力
- これが「数列の k 番目に小さい数」

💡ヒープとは？

👉 「常に一番小さい（または大きい）値をすぐ取り出せる箱」

配列の一種
ただし並び方に特別なルールがある
ソート済み配列とは違う

最小ヒープ（Min Heap）

今回使っているヒープの種類

親の値 ≤ 子の値
一番小さい値は必ず先頭（index 0）

 1
/ \
2 3
/ \
4 5

配列としては：

[1, 2, 3, 4, 5]

※ 見た目は配列、意味は木構造

① まずこの問題での「ヒープの役割」

この問題でやりたいことは：

P1, P2, P3 を掛けてできる数の中から
常に「次に小さい数」から順番に取り出したい

つまり：

「全部作ってからソート」 ❌（爆発する）
小さい順に1個ずつ取り出したい ⭕

👉 ここでヒープ（優先度付きキュー）が必要になる。

② ヒープとは（このコード限定の定義）

このコードにおける最小ヒープは：

「一番小さい値が必ず heap[0] にある配列」

だけを保証するデータ構造。

重要なのは👇

完全ソートはしていない
先頭だけ最小であればOK

③ コードの流れ × ヒープの中身

ここからコードを1行ずつ追いながら見ていく

🔹 STEP 1：初期化

const heap = new MinHeap();
const seen = new Set();
heap.push(1);
seen.add(1);

ヒープの状態

[1]

最初の数は必ず 1
当然これが最小

🔹 STEP 2：k 回ループ

for (let i = 0; i < k; i++) {
    current = heap.pop();

ここで起きていること

heap[0]（一番小さい数）を取り出す
ヒープから削除する
次に小さい数が先頭に来るよう並び替える

👉 「次に処理すべき最小の数」を確定させる

例：最初の pop

ヒープ：

[1]

current = 1;

🔹 STEP 3：取り出した数から次を生成

for (const p of [P1, P2, P3]) {
    const next = current * p;

意味:

「今いちばん小さい数 current から、次に来る候補を作る」

例えば：

current = 1
P1=2, P2=3, P3=5

生成される候補：

2, 3, 5

🔹 STEP 4：ヒープに突っ込む

if (!seen.has(next)) {
    seen.add(next);
    heap.push(next);
}

ここでのヒープ操作
① push(next)

this.heap.push(next);
this._bubbleUp(...)

👉 「とりあえず末尾に入れてから」
👉 「小さければ上に上げる」

例：2, 3, 5 を入れた後

ヒープ（形はどうでもいい）：

[2, 3, 5]

保証されているのは👇

heap[0] === 2
他は順不同

🔹 STEP 5：次のループへ

次の i でまたこれ👇

current = heap.pop();

今度は

current = 2

ヒープには

[3, 5]

が残る。

🔹 STEP 6：また増やす

2 * P1, 2 * P2, 2 * P3

例：

4, 6, 10

ヒープに追加すると（seenで重複除外）：

[3, 4, 5, 6, 10]

※ 配列の順番は違ってもOK
※ 先頭が最小であることだけが重要

④ ヒープの「正体」を一言で言うと

このコードにおけるヒープは：

「次に使う最小の数を、常に O(1) で取り出せる箱」

その代わり：

追加・削除のたびに、
_bubbleUp / _bubbleDown で
最小条件だけを回復している

コード	ヒープ的な意味
heap.push(x)	候補を箱に入れる
_bubbleUp	小さければ前に出す
heap.pop()	今いちばん小さい数を確定
_bubbleDown	次の最小を先頭に出す
heap[0]	常に最小値

📝まとめ

ポイント

全部作ってからソートはしない
- 数が指数的に増えるため非現実的
必要なのは
👉 「次に一番小さい数」を1つずつ確定すること
そのために
- 最小ヒープ（優先度付きキュー）
- Set（重複排除）
  を組み合わせて使う
ヒープとは
👉 「常に最小（最大）を素早く取り出せるデータ構造」
ヒープは配列で実装できるが
👉 意味的には木構造
pop() は
- 配列の shift() ではない
- 「最小値を確定させる操作」
_bubbleUp / _bubbleDown は
- ヒープ条件（親 ≤ 子）を保つための調整
Set は
- 正しさ（重複排除）
- 計算量削減
  の両方に必須
この問題の本質は：
「数を全部作る」のではなく、「必要な分だけ、小さい順に作る」

解法の方針（アルゴリズム）

最小ヒープを用意する
- 常に「一番小さい数」を取り出せる
Set を用意する
- 同じ数を二度入れないため
初期状態として
- ヒープに 1 を入れる
- Set に 1 を登録
k 回繰り返す
- ヒープから最小値を取り出す（これが current）
- current × P1, P2, P3 を計算
- まだ出ていない数だけ
  - Set に登録
  - ヒープに追加
k 回目に取り出した current が答え