ヒープソートの解説とPythonでの実装

ヒープソートは、効率的なソートアルゴリズムの一つであり、データを効率的に整列するための手法です。ヒープソートは、完全二分木を使用してソートを行うことで知られています。以下では、ヒープソートの仕組みとPythonでの実装方法について詳しく解説します。

ヒープソートの仕組み
ヒープソートの具体例
ヒープソートのPython実装

ヒープソートの仕組み

ヒープソートは、データを効率的にソートするアルゴリズムで、完全二分木（または二分ヒープ）を使用して実装されます。ヒープとは、親ノードが子ノードよりも大きい（または小さい）という性質を持つ木構造です。この性質により、最大値または最小値を迅速に見つけ出すことができます。

ヒープの構築 : 与えられたデータを最大ヒープ（または最小ヒープ）に変換します。
ソート処理 : 最大（または最小）要素を取り出し、ヒープから削除し、ソート済み配列の末尾に追加します。これを繰り返すことで、データ全体をソートします。

ヒープソートは、選択ソートや挿入ソートなどと比較して効率的なアルゴリズムの一つであり、平均時間計算量がO(n log n)であるため、大きなデータセットに対しても高速に動作します。

ヒープソートの具体例

配列[12,11,13,5,6,7]をヒープソートすることを考えます

1: 最初に与えられた配列を最大ヒープに変換します。これにより、[13,11,12,5,6,7]となります。

## 最大ヒープへの変換

Step 1: [12, 11, 13, 5, 6, 7]
             12
            /  \
          11    13
         / \   /
        5   6 7

Step 2: [13, 11, 12, 5, 6, 7]
             13
            /  \
          11    12
         / \   /
        5   6 7

2: 先頭の13を配列の最後の要素7と交換します。そして、未ソートの部分[11,7,12,5,6]に対して再び最大ヒープを作成します。これにより、[12,11,7,5,6]となります。

3: 先頭の12を配列の最後の要素6と交換し、未ソートの部分[11,6,7,5][に対して再び最大ヒープを作成します。これにより、[11,6,7,5]となります。

4: 先頭の11を配列の最後の要素5と交換し、未ソートの部分[6,5,7]に対して再び最大ヒープを作成します。これにより、[7,5,6]となります。

5: 先頭の7を配列の最後の要素6と交換し、未ソートの部分[5,6]に対して再び最大ヒープを作成します。これにより、[6,5]となります。

6: 最後に、先頭の6を配列の最後の要素5と交換します。

最終的に、ヒープソートを適用した結果、[5,6,7,11,12,13]とソートされた配列が得られます。

ヒープソートのPython実装

# ヒープソートの実装
def heapify(arr, n, i):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2

    if left < n and arr[i] < arr[left]:
        largest = left

    if right < n and arr[largest] < arr[right]:
        largest = right

    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, -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 = [12, 11, 13, 5, 6, 7]
heapSort(arr)
print("ソート済み配列：", arr)