《アルゴリズムを学ぶ》21.ヒープソート

# Overview
ヒープソート（Heap Sort） は、ヒープ（Heap）を利用して $O(N log N)$で動作するソートアルゴリズム 。ヒープを使って最大（または最小）値を取り出しながら配列をソートする。
[1.ヒープソートの基本概念](#1-ヒープソートの基本概念)
[2.ヒープソートのアルゴリズム](#2-ヒープソートのアルゴリズム)
[3.ヒープソートの応用](#3-ヒープソートの応用)
[4.典型問題を解いてみる](#4-典型問題を解いてみる)

# 1. ヒープソートの基本概念
ヒープソートは以下の2つのステップで構成される：
    1. 配列をヒープ（完全二分木）に変換
    2. ヒープの最大（または最小）値を取り出して、ソートを完了させる

### (1) ヒープソートの特徴
- 計算量：$O(N log N)$
ヒープの構築($O(N）$) + ヒープ操作($O(log N)$を N 回）

- 安定性：非安定ソート
同じ値の要素が、元の順番と異なる順番で出力される可能性がある

- メモリ使用量：$O(1)$（配列内での操作のみ）
追加の配列を使わず、内部でヒープ操作を行う

- 最悪計算量 $O(N log N)$ を保証
クイックソート（Quick Sort）は最悪 $O(N^2)$ の可能性があるが、ヒープソートは $O(N log N)$ で安定


# 2. ヒープソートのアルゴリズム
### (1) 配列をヒープに変換（Heapify）
- 完全二分木の形を作り、最大ヒープ（または最小ヒープ）を構築
- 子ノードが親ノードより大きくならないように調整
- ヒープ構築の計算量：$O(N)$
    
```python
def heapify(arr, n, i):
    largest = i  # 親ノード
    left = 2 * i + 1  # 左の子
    right = 2 * i + 2  # 右の子
    
    # 左の子が親より大きければ更新
    if left < n and arr[left] > arr[largest]:
        largest = left
    
    # 右の子が親より大きければ更新
    if right < n and arr[right] > arr[largest]:
        largest = right

    # 親ノードが最大でない場合、交換して再帰的に調整
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)
```

### (2) ヒープソートの実装
- ヒープを構築した後、ルート（最大値）を取り出して整列
- ヒープサイズを縮小しながら、残りの部分を再調整
```python
def heap_sort(arr):
    n = len(arr)

    # 1. 配列をヒープ化（最大ヒープを作成）
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    # 2. ヒープの最大要素を取り出し、配列末尾と交換しながらソート
    for i in range(n - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]  # 最大値を末尾に移動
        heapify(arr, i, 0)  # 残りのヒープを調整

# 使用例
arr = [4, 10, 3, 5, 1]
heap_sort(arr)
print(arr)  # 出力: [1, 3, 4, 5, 10]
```
- 計算量: O(N log N)
    - ヒープ構築：O(N)
    - ヒープから要素を削除して再構築：O(log N) を N 回実行 → O(N log N)

# 3. ヒープソートの応用
### (1) K 番目に小さい要素を求める
ヒープを使えば、配列内の 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 回最小値を取り出す

print(heapq.heappop(arr))  # 3番目に小さい値（7）
```
- O(N + K log N) で求められる

### (2) 大量データのソート
- 通常のソートより、O(N log N) で安定した性能を発揮
- 追加メモリを使用しないため、大規模データに向いている

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

## 例題1. ヒープソートの実装
**問題: N 個の整数をヒープソートでソートせよ。**
> [参考： ABC315 B - Heap Sort](https://atcoder.jp/contests/abc315/tasks/abc315_b)
<details><summary> 回答　</summary>

```python
N = int(input())
arr = list(map(int, input().split()))

heap_sort(arr)
print(*arr)
```
</details>

### 例題2. K 番目に小さい要素を求める
**問題: N 個の整数 A から K 番目に小さい値を求めよ。**
> [参考： ABC318 B - Kth Smallest Element](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()))

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

print(heapq.heappop(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>