Pythonのヒープソートとは？仕組みと実装方法をわかりやすく解説

ヒープソート（Heap Sort）は、二分ヒープというデータ構造を利用したソートアルゴリズムです。計算量が O(n log n) と安定しており、大量のデータを効率的に並べ替えられることから、実務や競技プログラミングでも広く活用されています。ヒープソートを理解するには、「完全二分木」と「二分ヒープ」という2つの基本概念を押さえておくことが重要です。

完全二分木とは

完全二分木とは、最後のレベルを除くすべてのレベルがノードで埋め尽くされている木構造のことです。さらに、最後のレベルのノードは必ず左側から順に詰められていなければなりません。

二分ヒープとは

二分ヒープは、完全二分木の特殊なケースであり、ノードの値に特定の順序制約を持つデータ構造です。二分ヒープには次の2種類があります。

• 最大ヒープ（Max Heap）：各レベルの親ノードが、その子ノードよりも大きい値を持つヒープ。
• 最小ヒープ（Min Heap）：各レベルの親ノードが、その子ノードよりも小さい値を持つヒープ。

完全二分木の配列表現

二分ヒープは、メモリを効率的に使える配列として表現できます。インデックスが0始まりの場合、親ノードがインデックス i に格納されているとき、左の子ノードは「2 * i + 1」、右の子ノードは「2 * i + 2」で求められます。逆に、子ノードから親ノードを求める場合は「(i - 1) // 2」で計算できます。

ヒープソートのアルゴリズム

1. 完全二分木から最大ヒープを構築します。
2. ルート（最大値）を取り出してヒープの末尾の要素と入れ替え、ヒープのサイズを1減らしたうえで、残りのノードで再度最大ヒープを構築します。
3. ノードが1つだけ残るまで、手順2を繰り返します。

最大ヒープの構築（heapify）

まず、完全二分木から最大ヒープを構築するコードを見てみましょう。この処理では、ルートと2つの子ノードを比較し、最大の要素がルートでなければ、その要素をルートと入れ替えます。これは再帰的な処理で、子ノードより小さいルートは、正しい位置に到達するまで下位の部分木との比較と入れ替えが繰り返されます。

次のコードは、ソート対象の配列（＝完全二分木）から最大ヒープを構築する関数です。

def heapify(arr, n, i):
    # ルートと子ノードの中で最大の要素を探す
    largest = i
    l = 2 * i + 1
    r = 2 * i + 2
    if l < n and arr[i] < arr[l]:
        largest = l
    if r < n and arr[largest] < arr[r]:
        largest = r
    # 最大要素がルートでなければ入れ替え、ヒープ化を継続
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

ヒープソートの実装

最大ヒープが完成したら、次の手順でソートを行います。

• ルート（最大値）とヒープの末尾の要素を入れ替えます。
• ヒープのサイズを1減らします（これにより最大値が最後尾に確定し、以降その要素は考慮しなくなります）。
• 末尾の要素を除いた残りで最大ヒープを再構築します。
• 要素が1つだけ残るまで、上記の手順を繰り返します。

for i in range(n-1, 0, -1):
    # ルートと末尾の要素を入れ替える
    arr[i], arr[0] = arr[0], arr[i]

    # ルート要素をヒープ化する
    heapify(arr, i, 0)

Pythonによるヒープソートの完全なプログラム

ここまでの内容をまとめた、Pythonのヒープソートの完全なプログラムは以下の通りです。

def heapify(arr, n, i):
    # ルートと子ノードの中で最大の要素を探す
    largest = i
    l = 2 * i + 1
    r = 2 * i + 2
    if l < n and arr[i] < arr[l]:
        largest = l
    if r < n and arr[largest] < arr[r]:
        largest = r
    # 最大要素がルートでなければ入れ替え、ヒープ化を継続
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

def heapSort(arr):
    n = len(arr)
    # 最大ヒープを構築
    for i in range(n//2, -1, -1):
        heapify(arr, n, i)
    for i in range(n-1, 0, -1):
        # ルートと末尾の要素を入れ替える
        arr[i], arr[0] = arr[0], arr[i]
        # ルート要素をヒープ化する
        heapify(arr, i, 0)

arr = [1, 12, 9, 5, 6, 10]
heapSort(arr)
n = len(arr)
print("Sorted array is")
for i in range(n):
    print(arr[i], end=' ')

まとめ

ヒープソートは、二分ヒープの性質を利用して最大値（または最小値）を繰り返し取り出すことで配列を整列するアルゴリズムです。最悪ケースでも O(n log n) の時間計算量を保証し、追加のメモリがほぼ不要（in-placeソート）という大きな特徴があります。一方で、安定ソートではない点や、クイックソートと比べて定数倍の速度で劣る場合がある点には注意が必要です。

時間計算量：O(n log n)