Pythonのヒープソートアルゴリズムの実装方法を教えてください

ヒープソートアルゴリズムの実行手順は次のとおりです。

1. 待ソート対象を最大ヒープに構築する。最後の葉でないノードから開始し、現在のノードと子ノードを比較する。現在のノードの値が子ノードの値より小さい場合、両者を入れ替え、次のノードと比較を続ける。現在のノードの値が子ノードの値以上となるまで繰り返す。
2. 一番上の要素と配列の最後の要素を入れ替える：一番上の要素とこの配列の最後の要素を入れ替えて、一番大きい要素がその配列の末尾に来るようにする。
3. 残りの要素を最大ヒープの性質を満たすように再調整する: すべての要素がソートされるまでステップ1とステップ2を繰り返します。

下記は 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)

    return arr


# 测试
arr = [12, 11, 13, 5, 6, 7]
sorted_arr = heapSort(arr)
print("排序结果:", sorted_arr)

結果は [5, 6, 7, 11, 12, 13] です。