ヒープソートの仕組み・コード・計算量をわかりやすく解説

考え方を平易に説明

ヒープソートは、最大値をより速く見つける方法を使った選択ソートです。選択ソートは毎回、未ソート部分全体を O(n) で走査します。ヒープソートは未ソート部分をヒープとして保つため、最大値は常にインデックス 0 にあり、それを取り除いた後の順序の回復は O(log n) で済みます。

二分ヒープは、ポインタを使わず、普通の配列に格納されます。インデックス i の要素については次のようになります。

• 左の子は 2*i + 1、右の子は 2*i + 2 にあります。
• 親は (i - 1) // 2 にあります。
• 最大ヒープでは、すべての親が子以上なので、最大の要素はインデックス 0 にあります。

1. 最後のものから 0 番に向かって、葉でないすべてのノードをシフトダウンして、配列から最大ヒープを作ります。
2. 根（最大値）をヒープの最後の要素と交換します。その要素は最終位置に収まります。
3. ヒープを1つ縮め、ヒープの性質が再び成り立つまで、新しい根をシフトダウンします。
4. ヒープの要素が1つになるまで、手順2と3を繰り返します。

具体例をステップごとに見る

[4, 10, 3, 5, 1] をソートします。バーの後ろの要素はソート済みで確定です。

Pythonでの実装

def sift_down(a, root, end):
    """Restore the max-heap property for a[root..end-1]."""
    while True:
        child = 2 * root + 1
        if child >= end:
            return
        if child + 1 < end and a[child + 1] > a[child]:
            child += 1                      # pick the larger child
        if a[root] >= a[child]:
            return
        a[root], a[child] = a[child], a[root]
        root = child

def heapsort(a):
    """Sort list a in place, ascending."""
    n = len(a)
    for i in range(n // 2 - 1, -1, -1):     # build the max-heap
        sift_down(a, i, n)
    for end in range(n - 1, 0, -1):
        a[0], a[end] = a[end], a[0]         # move the max to the end
        sift_down(a, 0, end)
    return a

print(heapsort([4, 10, 3, 5, 1]))   # [1, 3, 4, 5, 10]
print(heapsort([2, 2, 1]))          # [1, 2, 2]

Pythonの heapq モジュールは、普通のリスト上の最小ヒープを提供します。すべての要素を順に取り出せばソート済みリストが得られ、これは（インプレースではない）短いヒープソートになります。

import heapq

def heapsort_heapq(items):
    h = list(items)
    heapq.heapify(h)                       # O(n)
    return [heapq.heappop(h) for _ in range(len(h))]

print(heapsort_heapq([4, 10, 3, 5, 1]))     # [1, 3, 4, 5, 10]
print(heapq.nlargest(2, [4, 10, 3, 5, 1]))  # [10, 5]

時間計算量と空間計算量

ボトムアップのヒープ構築は O(n log n) ではなく O(n) です。完全二分木のノードの高さの総和が O(n) になるためです。全体の時間を支配するのは、取り出しの段階です。

ヒープソートと他のソートの比較

ヒープソートは安定ではありません。根を末尾に交換する際に、同じキーを持つ他の要素を飛び越えて要素が運ばれてしまうことがあるためです。主な強みは、最悪ケースの O(n log n) の保証と追加の空間 O(1) を両立している点で、これはクイックソートにもマージソートにもありません。弱点はメモリアクセスです。インデックス i と 2*i + 1 の間を飛び回るため CPU キャッシュをうまく使えず、うまく実装されたクイックソートよりも通常は遅くなります。イントロソートは、クイックソートの再帰が深くなりすぎたときのフォールバックとして、ヒープソートを使います。

派生と、よくある間違い

• 部分ソート：大きいほうから k 個だけが欲しい場合は、ヒープを作って k 回取り出します。計算量は O(n + k log n) です。Pythonでは heapq.nlargest と heapq.nsmallest がこれを行います。
• ストリームからの上位 k 件：サイズ k の最小ヒープを保ち、新しい要素ごとに push または置き換えます。時間は O(n log k)、メモリは O(k) です。
• ボトムアップヒープソートは、穴をまず葉までシフトダウンしてから上に戻すことで、比較回数を減らします。
• スムースソートは、ダイクストラによるヒープベースの派生で、すでにソート済みの入力では O(n) で動作しますが、複雑なためほとんど使われません。

ヒープソートを使う場面

追加のメモリなしで、最悪ケースの O(n log n) が保証されている必要がある場合に使います。たとえば組み込みシステムやリアルタイムシステム、あるいは他のソートの内部の安全なフォールバックとしてです。日常的なPythonコードでは、安定で、一般的なデータでより高速な sorted() を使ってください。ソートよりも、ヒープそのもののほうが役に立ちます。優先度付きキュー、ダイクストラ法による最短経路、スケジューラ、k 個のソート済みリストのマージ（heapq.merge）、上位 k 個の値の探索は、すべてヒープを土台にしています。面接では、ヒープのインデックスの公式、ヒープの構築が O(n) になる理由、上位 k 件の問題がよく問われます。