0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@Haru_K0720(Haru_K)

「ある数でつくられた数列」を解くために：part5　💡ヒープ (JSのクラスで再現/解説)

Posted at

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


問題概要

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



入力例：

2 3 5
3
4
5
6

出力例：

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 は「消費する」ための操作
0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?