《アルゴリズムを学ぶ》19.ヒープ

# Overview
ヒープ（Heap） は、最小値または最大値を効率的に管理できるデータ構造 であり、優先度付きキュー（Priority Queue） を実現するために使われる。
Python では `heapq` モジュールを使うと、最小ヒープ（Min-Heap）を簡単に実装 できる。
[1.ヒープの基本](#1-ヒープの基本)
[2.最大ヒープ（Max-Heap）の実装](#2-最大ヒープmax-heapの実装)
[3.ヒープの応用](#3-ヒープの応用)
[4.典型問題を解いてみる](#4-典型問題を解いてみる)

# 1. ヒープの基本
### (1) ヒープとは？
- 最小ヒープ（Min-Heap）: 常に最小の要素が `heap[0]` に保持される
- 最大ヒープ（Max-Heap）: 常に最大の要素が `heap[0]` に保持される
- ヒープは「完全二分木（Complete Binary Tree）」
二分木（Binary Tree）: 各ノードが 最大2つの子 を持つ木
完全二分木（Complete Binary Tree）:左から順に詰めて ノードを配置する
最下段以外はすべて埋まっている
最小値（または最大値）がルート（頂点）に来る
親ノードの値は子ノードの値より小さい（または大きい）
例: 最小ヒープ（Min-Heap）の木構造
    ```markdown
          1
         / \
        3   4
       / \  /
      7   6 5
    ```



- 優先度付きキューを実現するために使用される

### (2) Python の heapq の基本操作
```python
import heapq

heap = []

# 要素を追加（push）
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
heapq.heappush(heap, 4)

print(heap)  # [1, 3, 4]（最小値が先頭にくる）

# 最小値を取得（pop）
print(heapq.heappop(heap))  # 1 最小値を取得しながら削除
print(heap)  # [3, 4]
```
- リストとは異なり、順番が保証されるのは最小値のみ

# 2. 最大ヒープ（Max-Heap）の実装
Python の `heapq` は デフォルトで最小ヒープ なので、最大ヒープを作るには 負の値を使う。

```python
import heapq

heap = []

# 負の値を追加（最大値を管理）
heapq.heappush(heap, -3)
heapq.heappush(heap, -1)
heapq.heappush(heap, -4)

# 最大値を取得
print(-heapq.heappop(heap))  # 4
print(-heapq.heappop(heap))  # 3
```
- 負の値を入れることで、最大値が heap[0] に来る
- `heapq.heappop()` の戻り値に -1 をかけると、元の正の値を取得できる

# 3. ヒープの応用
### (1) N 個の要素の中から K 番目に小さい要素を求める
```python
import heapq

arr = [7, 10, 4, 3, 20, 15]
k = 3

heapq.heapify(arr)  # 配列をヒープ化
for _ in range(k - 1):
    heapq.heappop(arr)  # k-1 回 pop する

print(heapq.heappop(arr))  # 3番目に小さい値（7）
```

### (2) N 個の要素の中から K 個の最大値を求める
```python
import heapq

arr = [7, 10, 4, 3, 20, 15]
k = 3

print(heapq.nlargest(k, arr))  # [20, 15, 10]
```

- `heapq.nlargest(k, arr)` を使うと、最大 K 個の要素を O(K log N) で取得

### (3) 2つの最小値を合成する（最小コストで作る）
```python
import heapq

N = int(input())  # 数列の要素数
A = list(map(int, input().split()))  # 数列

heapq.heapify(A)  # 配列を最小ヒープに変換

cost = 0  # 合成コストの合計
while len(A) > 1:
    x = heapq.heappop(A)  # 最小値を取り出す
    y = heapq.heappop(A)  # 2番目に小さい値を取り出す
    cost += x + y  # 合成コストを追加
    heapq.heappush(A, x + y)  # 合成した値をヒープに戻す

print(cost)  # 最小合成コスト
```
- 貪欲法（Greedy Algorithm）を用いた最小コスト合成アルゴリズム
- ロジックの動作手順
- ```ini
    # 例として、以下のリストを考えます：
    A = [1, 2, 3, 4, 5]

    # ステップ 1: 初期状態
    heapq.heapify(A) # 最小ヒープに変換：[1, 2, 3, 4, 5] （最小値が先頭）

    # ステップ２〜５はwhile内の処理
    # ステップ 2: 2つの最小値を合成
    # 1. 最小値 1 を取り出す
    # 2. 次に小さい 2 を取り出す
    # 3. 1 + 2 = 3 を合成コストに加算（現在の合成コスト: 3）
    # 4. 3 をヒープに戻す

    # ヒープ: [3, 3, 5, 4]

    # ステップ 3: 2つの最小値を合成
    # 1. 3 を取り出す
    # 2. 3 を取り出す
    # 3. 3 + 3 = 6 を合成コストに加算（合計: 3 + 6 = 9）
    # 4. 6 をヒープに戻す

    # ヒープ: [4, 5, 6]

    # ステップ 4: 2つの最小値を合成
    # 1. 4 を取り出す
    # 2. 5 を取り出す
    # 3. 4 + 5 = 9 を合成コストに加算（合計: 9 + 9 = 18）
    # 4. 9 をヒープに戻す

    # ヒープ: [6, 9]

    # ステップ 5: 最後の 2 つを合成
    # 1. 6 を取り出す
    # 2. 9 を取り出す
    # 3. 6 + 9 = 15 を合成コストに加算（合計: 18 + 15 = 33）

    # ヒープ: []（すべて合成完了）

    # 最終的な合成コスト: 33
    ```

# 4. 典型問題を解いてみる

### 例題1. K 番目に小さい値を求める
**問題: N 個の整数 A から K 番目に小さい値を求めよ。**
> [参考： ABC315 B - Kth Smallest Element](https://atcoder.jp/contests/abc315/tasks/abc315_b)
<details><summary> 回答　</summary>

```python
import heapq

N, K = map(int, input().split())
A = list(map(int, input().split()))

heapq.heapify(A)
for _ in range(K - 1):
    heapq.heappop(A)

print(heapq.heappop(A))
```
</details>

### 例題2. K 個の最大値を求める
**問題: N 個の整数 A から K 個の最大値を求めよ。**
> [参考： ABC318 B - K Largest Elements](https://atcoder.jp/contests/abc318/tasks/abc318_b)
<details><summary> 回答　</summary>

```python
import heapq

N, K = map(int, input().split())
A = list(map(int, input().split()))

print(*heapq.nlargest(K, A))
```
</details>

### 例題3. 優先度付きキューのシミュレーション
**問題: N 個のクエリが与えられる。insert x で x を追加し、pop で最小値を取り出せ。**
> [参考： ABC319 C - Priority Queue](https://atcoder.jp/contests/abc319/tasks/abc319_c)
<details><summary> 回答　</summary>

```python
import heapq

N = int(input())
heap = []

for _ in range(N):
    query = input().split()
    if query[0] == "insert":
        heapq.heappush(heap, int(query[1]))
    elif query[0] == "pop":
        print(heapq.heappop(heap))
```
</details>

### 例題4. 2つの最小値を合成する
**問題: N 個の数を最小コストで合成せよ。**
> [参考： ABC320 B - Minimum Cost Merge](https://atcoder.jp/contests/abc320/tasks/abc320_b)
<details><summary> 回答　</summary>

```python
import heapq

N = int(input())
A = list(map(int, input().split()))
heapq.heapify(A)

cost = 0
while len(A) > 1:
    x = heapq.heappop(A)
    y = heapq.heappop(A)
    cost += x + y
    heapq.heappush(A, x + y)

print(cost)
```
</details>