Day 8: ヒープと優先度キュー

今日学ぶこと

• ヒープの概念と性質
• 最小ヒープと最大ヒープの実装
• 優先度キューの仕組み
• ヒープソートの実装

---

ヒープとは

ヒープ（Heap） は完全二分木で、親ノードの値が子ノードの値に対して特定の関係を持ちます。

flowchart TB
    subgraph MinHeap["最小ヒープ（親 ≤ 子）"]
        M1["1"] --> M2["3"]
        M1 --> M3["2"]
        M2 --> M4["7"]
        M2 --> M5["6"]
        M3 --> M6["5"]
        M3 --> M7["4"]
    end
    subgraph MaxHeap["最大ヒープ（親 ≥ 子）"]
        X7["7"] --> X5["5"]
        X7 --> X6["6"]
        X5 --> X1["1"]
        X5 --> X3["3"]
        X6 --> X2["2"]
        X6 --> X4["4"]
    end
    style MinHeap fill:#3b82f6,color:#fff
    style MaxHeap fill:#8b5cf6,color:#fff

ヒープの性質

1. 完全二分木: 最下段を除いて全てのレベルが埋まっている
2. ヒープ条件: 最小ヒープでは親 ≤ 子、最大ヒープでは親 ≥ 子

---

配列によるヒープの表現

ヒープは配列で効率的に表現できます。

Index:    0  1  2  3  4  5  6
Array:   [1, 3, 2, 7, 6, 5, 4]

関係	インデックス
親	Math.floor((i - 1) / 2)
左の子	2 * i + 1
右の子	2 * i + 2

---

最小ヒープの実装

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

  // Helper methods
  _parentIndex(i) { return Math.floor((i - 1) / 2); }
  _leftChildIndex(i) { return 2 * i + 1; }
  _rightChildIndex(i) { return 2 * i + 2; }
  _swap(i, j) { [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]]; }

  // Peek at minimum: O(1)
  peek() {
    return this.heap[0];
  }

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

  // Insert: O(log n)
  insert(value) {
    this.heap.push(value);
    this._bubbleUp(this.heap.length - 1);
  }

  _bubbleUp(index) {
    while (index > 0) {
      const parent = this._parentIndex(index);
      if (this.heap[parent] <= this.heap[index]) break;
      this._swap(parent, index);
      index = parent;
    }
  }

  // Extract minimum: O(log n)
  extractMin() {
    if (this.heap.length === 0) return undefined;
    if (this.heap.length === 1) return this.heap.pop();

    const min = this.heap[0];
    this.heap[0] = this.heap.pop();
    this._bubbleDown(0);
    return min;
  }

  _bubbleDown(index) {
    const length = this.heap.length;
    while (true) {
      let smallest = index;
      const left = this._leftChildIndex(index);
      const right = this._rightChildIndex(index);

      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._swap(index, smallest);
      index = smallest;
    }
  }
}

const heap = new MinHeap();
[5, 3, 8, 1, 2, 7].forEach(v => heap.insert(v));
console.log(heap.peek());       // 1
console.log(heap.extractMin()); // 1
console.log(heap.extractMin()); // 2
console.log(heap.extractMin()); // 3

---

ヒープの操作の流れ

挿入（Insert）

flowchart TB
    subgraph Before["挿入前"]
        B1["1"] --> B3["3"]
        B1 --> B5["5"]
        B3 --> B7["7"]
        B3 --> B6["6"]
    end
    subgraph After["2を挿入後（bubble up）"]
        A1["1"] --> A2["2"]
        A1 --> A5["5"]
        A2 --> A7["7"]
        A2 --> A6["6"]
        A5 --> A3["3"]
    end
    style Before fill:#3b82f6,color:#fff
    style After fill:#22c55e,color:#fff

最小値の取り出し（Extract Min）

flowchart TB
    subgraph Before["取り出し前"]
        B1["1"] --> B3["3"]
        B1 --> B5["5"]
        B3 --> B7["7"]
    end
    subgraph After["1を取り出し後（bubble down）"]
        A3["3"] --> A7["7"]
        A3 --> A5["5"]
    end
    style Before fill:#3b82f6,color:#fff
    style After fill:#22c55e,color:#fff

---

優先度キュー

優先度キュー（Priority Queue） は、要素に優先度が付いており、最も優先度の高い要素が先に取り出されるデータ構造です。ヒープを使って実装します。

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

  _parentIndex(i) { return Math.floor((i - 1) / 2); }
  _leftChildIndex(i) { return 2 * i + 1; }
  _rightChildIndex(i) { return 2 * i + 2; }
  _swap(i, j) { [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]]; }

  // Enqueue with priority (lower number = higher priority)
  enqueue(value, priority) {
    this.heap.push({ value, priority });
    this._bubbleUp(this.heap.length - 1);
  }

  _bubbleUp(index) {
    while (index > 0) {
      const parent = this._parentIndex(index);
      if (this.heap[parent].priority <= this.heap[index].priority) break;
      this._swap(parent, index);
      index = parent;
    }
  }

  // Dequeue highest priority element
  dequeue() {
    if (this.heap.length === 0) return undefined;
    if (this.heap.length === 1) return this.heap.pop();

    const top = this.heap[0];
    this.heap[0] = this.heap.pop();
    this._bubbleDown(0);
    return top;
  }

  _bubbleDown(index) {
    const length = this.heap.length;
    while (true) {
      let smallest = index;
      const left = this._leftChildIndex(index);
      const right = this._rightChildIndex(index);

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

      this._swap(index, smallest);
      index = smallest;
    }
  }

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

  isEmpty() {
    return this.heap.length === 0;
  }
}

const pq = new PriorityQueue();
pq.enqueue("Low priority task", 5);
pq.enqueue("Critical bug fix", 1);
pq.enqueue("Feature request", 3);
pq.enqueue("Urgent issue", 2);

while (!pq.isEmpty()) {
  const item = pq.dequeue();
  console.log(`[Priority ${item.priority}] ${item.value}`);
}
// [Priority 1] Critical bug fix
// [Priority 2] Urgent issue
// [Priority 3] Feature request
// [Priority 5] Low priority task

---

ヒープソート

ヒープを使ったソートアルゴリズムです。

function heapSort(arr) {
  const n = arr.length;

  // Build max heap
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    heapify(arr, n, i);
  }

  // Extract elements one by one
  for (let i = n - 1; i > 0; i--) {
    [arr[0], arr[i]] = [arr[i], arr[0]]; // Move max to end
    heapify(arr, i, 0); // Restore heap property
  }

  return arr;
}

function heapify(arr, n, i) {
  let largest = i;
  const left = 2 * i + 1;
  const right = 2 * i + 2;

  if (left < n && arr[left] > arr[largest]) largest = left;
  if (right < n && arr[right] > arr[largest]) largest = right;

  if (largest !== i) {
    [arr[i], arr[largest]] = [arr[largest], arr[i]];
    heapify(arr, n, largest);
  }
}

console.log(heapSort([12, 11, 13, 5, 6, 7]));
// [5, 6, 7, 11, 12, 13]

特性	値
時間計算量	O(n log n)
空間計算量	O(1)（インプレース）
安定	No

---

実践例：K個の最大/最小要素

// Find k largest elements using a min heap
function kLargest(arr, k) {
  const minHeap = new MinHeap();

  for (const num of arr) {
    minHeap.insert(num);
    if (minHeap.size > k) {
      minHeap.extractMin();
    }
  }

  const result = [];
  while (minHeap.size > 0) {
    result.push(minHeap.extractMin());
  }
  return result;
}

console.log(kLargest([3, 1, 5, 12, 2, 11], 3)); // [5, 11, 12]

---

ヒープの計算量

操作	計算量
挿入（insert）	O(log n)
最小/最大の取得（peek）	O(1)
最小/最大の取り出し（extract）	O(log n)
ヒープの構築（buildHeap）	O(n)
ヒープソート	O(n log n)

---

まとめ

概念	説明
ヒープ	完全二分木で親子間に順序関係を持つ
最小ヒープ	親 ≤ 子、根が最小値
最大ヒープ	親 ≥ 子、根が最大値
優先度キュー	優先度に基づいて要素を取り出す
ヒープソート	ヒープを使ったO(n log n)のインプレースソート

重要ポイント

1. ヒープは配列で効率的に表現できる
2. 挿入と取り出しは O(log n)、最小/最大値の参照は O(1)
3. 優先度キューはヒープで実装するのが一般的
4. ヒープソートはインプレースで O(n log n) だが不安定

---

練習問題

問題1: 基本

最大ヒープを実装してください（MinHeapの比較条件を逆にする）。

問題2: 応用

データストリームの中央値をリアルタイムで求める仕組みを、2つのヒープ（最大ヒープと最小ヒープ）を使って実装してください。

チャレンジ問題

K個のソート済み配列をマージして1つのソート済み配列にする関数を、優先度キューを使って実装してください。

---

参考リンク

• Wikipedia - Heap
• Visualgo - Heap
• Wikipedia - Heapsort

---

次回予告: Day 9では「グラフ」について学びます。ノード間の関係を表現する強力なデータ構造を理解しましょう。