ヒープソートはどのように機能しますか？

Question

ヒープソートはどのように機能しますか？

Accepted Answer

**ヒープソート**は配列から**バイナリヒープ**を構築し、その後、最大値を繰り返し抽出してソート済みの順序を生成します。**O(n log n)**で実行され、**インプレース**です。

## アイデア

マックスヒープは、最大の要素をルートに保持します。ヒープを構築し（O(n)）、ルートを末尾と交換し、ヒープを縮小し、リヒープ化（sift down）を行います — n回。

## 例

```python
import heapq

def heap_sort(arr):
    heapq.heapify(arr)               # min-heap in O(n)
    return [heapq.heappop(arr)       # pop smallest n times
            for _ in range(len(arr))]

heap_sort([5, 2, 8, 1, 3])           # -> [1, 2, 3, 5, 8]
```

古典的な実装は、配列内でsift downを行うことでインプレースで実行します。

## 計算量

- **時間:** すべてのケースでO(n log n)。**空間:** O(1)インプレース。

## いつ使うか / 落とし穴

**保証されたO(n log n)**と**O(1)の追加メモリ**が必要な場合に使用します（マージソートはO(n)が必要; クイックソートはO(n²)のリスク）。**安定ではなく**、キャッシュ局所性が悪いため、実際にはクイックソートより遅いことが多いです。同じヒープが**優先度キュー**とトップk要素の検索を支えています。

## なぜ重要なのか

ヒープソートは、ワーストケースがO(n log n)かつインプレースの唯一の一般的なソート方式であり、メモリ制約のある環境や保証された限界の設定で価値があります。

基層のヒープ構造は広く有用です — 優先度キュー、ダイクストラのアルゴリズム、ストリーミングトップk。

適切なデータ構造がアルゴリズムを効率的にするというアイデアを定着させます。