ヒープソート

ヒープソート#

ヒープソート（heap sort） はヒープデータ構造を利用したソートアルゴリズム。最大ヒープを構築し、根（最大値）を末尾と交換してヒープサイズを縮小する操作を繰り返す。

計算量

最悪時間計算量

\(O(n \log n)\)

平均時間計算量

\(O(n \log n)\)

最良時間計算量

\(O(n \log n)\)

空間計算量

\(O(1)\)（in-place）

特徴

  • 非安定ソート

  • in-place かつ最悪でも \(O(n \log n)\) が保証される（クイックソートと異なる）

  • キャッシュ効率が悪くクイックソートより実用上遅いことが多い

  • ヒープデータ構造については ヒープ を参照

アルゴリズム#

配列をバイナリヒープとして扱う。インデックス i の子は 2i+1、2i+2。

  1. Build Max-Heap: 配列全体を最大ヒープに変換する \(O(n)\)

  2. Extract: 根（最大値）を末尾と交換し、ヒープサイズを1減らしてヒープ性を回復（sift-down）する \(O(\log n)\)

  3. ステップ2を \(n-1\) 回繰り返す

def heap_sort(arr: list) -> list:
    a = arr.copy()
    n = len(a)

    # Build Max-Heap: 末尾の非葉ノードから根に向かって sift-down
    for i in range(n // 2 - 1, -1, -1):
        _sift_down(a, i, n)

    # 根（最大値）を末尾と交換しながら縮小
    for end in range(n - 1, 0, -1):
        a[0], a[end] = a[end], a[0]
        _sift_down(a, 0, end)

    return a

def _sift_down(a: list, i: int, heap_size: int) -> None:
    """インデックス i の要素をヒープ性が回復するまで下げる"""
    while True:
        largest = i
        left = 2 * i + 1
        right = 2 * i + 2
        if left < heap_size and a[left] > a[largest]:
            largest = left
        if right < heap_size and a[right] > a[largest]:
            largest = right
        if largest == i:
            break
        a[i], a[largest] = a[largest], a[i]
        i = largest

import random

data = [12, 11, 13, 5, 6, 7]
print("入力:", data)
print("出力:", heap_sort(data))

random.seed(4)
large = random.sample(range(10000), 100)
assert heap_sort(large) == sorted(large)
print("ランダム100件: OK")

# 最悪ケース（既ソート済み）でも O(n log n)
sorted_data = list(range(500))
assert heap_sort(sorted_data) == sorted_data
print("既ソート済み500件: OK")

入力: [12, 11, 13, 5, 6, 7]
出力: [5, 6, 7, 11, 12, 13]
ランダム100件: OK
既ソート済み500件: OK

Python の heapq を使った実装#

Python 標準ライブラリの heapq は最小ヒープを提供する。

import heapq

def heap_sort_heapq(arr: list) -> list:
    h = arr.copy()
    heapq.heapify(h)          # O(n)
    return [heapq.heappop(h) for _ in range(len(h))]  # O(n log n)

data = [12, 11, 13, 5, 6, 7]
print(heap_sort_heapq(data))
assert heap_sort_heapq(data) == sorted(data)

[5, 6, 7, 11, 12, 13]

応用：Top-K 問題#

配列から上位 \(k\) 件を求める場合、全体をソートするよりサイズ \(k\) の最小ヒープを維持する方が効率的。計算量 \(O(n \log k)\)。

import heapq

def top_k_largest(arr: list, k: int) -> list:
    """配列から上位 k 件を返す（降順）"""
    return heapq.nlargest(k, arr)

def top_k_largest_manual(arr: list, k: int) -> list:
    """サイズ k の最小ヒープで手動実装"""
    heap = arr[:k]
    heapq.heapify(heap)
    for x in arr[k:]:
        if x > heap[0]:
            heapq.heapreplace(heap, x)
    return sorted(heap, reverse=True)

data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
k = 3
print(f"データ: {data}")
print(f"Top-{k}: {top_k_largest(data, k)}")
print(f"Top-{k} (手動): {top_k_largest_manual(data, k)}")

データ: [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
Top-3: [9, 6, 5]
Top-3 (手動): [9, 6, 5]
Contents