Pythonでヒープソートを実装する方法をわかりやすく解説

この記事では、配列をヒープソート（Heap Sort）のアルゴリズムを使って並べ替える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, -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 = [2,5,3,8,6,5,4,7]
heapSort(arr)
n = len(arr)
print("Sorted array is")
for i in range(n):
    print(arr[i], end=" ")

出力結果

Sorted array is
2 3 4 5 5 6 7 8

コードのポイント

このアルゴリズムの中核となるのは heapify 関数です。指定したノードを起点として、左右の子ノードと値を比較し、最も大きい値を親の位置に持ってくることで、部分的なヒープ条件を満たすようにします。条件を満たさない場合は要素を交換し、再帰的に下位のノードへ処理を伝播させます。

heapSort 関数では、まず配列全体を最大ヒープに変換します（計算量：O(n)）。その後、先頭の最大値を末尾の要素と交換してはヒープサイズを1ずつ縮めながら再ヒープ化する操作を繰り返します。この段階の計算量は O(n log n) であり、ヒープソート全体の平均・最悪計算量は O(n log n) となります。

すべての変数はローカルスコープ内で宣言されており、各ステップでの参照関係は図のように整理できます。

まとめ

この記事では、Pythonを使ってヒープソートを実装する方法を学びました。ヒープソートは追加のメモリ領域をほとんど必要としないインプレースなソートアルゴリズムであり、最悪ケースでも O(n log n) の性能を保証する点が大きな特徴です。クイックソートと比べると定数倍は遅いものの、安定した計算量が必要な場面で非常に有用です。