ヒープソートの実装と利用方法

ヒープソートは、比較ベースのソートアルゴリズムの一つで、ヒープ（特にバイナリヒープ）データ構造を利用してデータをソートします。ヒープソートは、最悪の場合でもO(n log n)の時間計算量を持ち、空間計算量はO(1)であるため、効率的なソートアルゴリズムとして広く使用されています。

ヒープソートの基本概念

ヒープソートは、以下の2つの主要なステップから構成されます。

1. ヒープの構築: 入力配列から最大ヒープまたは最小ヒープを構築します。
2. ソートの実行: ヒープのトップ要素（最大値または最小値）を取り出し、配列の末尾と交換して、ヒープのサイズを1減らします。これを繰り返すことで、配列がソートされます。

ヒープの構築

ここでは、最大ヒープを構築する関数を実装します。最大ヒープでは、親ノードの値が子ノードの値よりも大きいという性質があります。

最大ヒープの構築

まず、最大ヒープを構築するためのヘルパー関数を実装します。この関数は、与えられたインデックスを持つノードを根とする部分ヒープが最大ヒープの条件を満たすように調整します。

def heapify(arr, n, i):
    largest = i  # 親ノード
    left = 2 * i + 1  # 左子ノード
    right = 2 * i + 2  # 右子ノード

    # 左子ノードが親ノードより大きい場合
    if left < n and arr[left] > arr[largest]:
        largest = left

    # 右子ノードが現在の最大ノードより大きい場合
    if right < n and arr[right] > arr[largest]:
        largest = right

    # 最大ノードが親ノードでない場合
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]  # スワップ

        # 再帰的にヒープ化
        heapify(arr, n, largest)

ヒープソートの実装

次に、ヒープソートのメイン関数を実装します。この関数では、まず配列から最大ヒープを構築し、その後、ヒープから要素を取り出してソートを行います。

def heap_sort(arr):
    n = len(arr)

    # 最大ヒープの構築
    for i in range(n // 2 - 1, -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)

ヒープソートの利用方法

最後に、ヒープソートを使って配列をソートする方法を示します。以下のコードは、ヒープソートを用いて数値のリストをソートする例です。

if __name__ == "__main__":
    arr = [12, 11, 13, 5, 6, 7]
    print("元の配列:", arr)

    heap_sort(arr)

    print("ソートされた配列:", arr)

コードの解説

1. heapify関数: 配列をヒープ化するための関数です。親ノードとその子ノードを比較して、最大ヒープの条件を満たすように調整します。

2. heap_sort関数: ヒープソートを実行する関数です。最初に配列を最大ヒープに変換し、その後、ヒープから要素を取り出してソートします。

3. メインブロック: ヒープソートの実行をテストするためのコードです。元の配列とソートされた配列を表示します。

まとめ

ヒープソートは、効率的にデータをソートするための強力なアルゴリズムです。最大ヒープを利用することにより、最大値を簡単に取り出すことができ、ソートプロセスを効率的に進めることができます。ヒープソートを理解することで、他のアルゴリズムやデータ構造の理解も深まります。