Python实现堆排序算法

​

 Python实现堆排序算法

以下是使用 Python 实现堆排序算法的示例代码：

# 调整堆，使以root为根节点的树满足堆的性质
def heapify(arr, n, root):
    largest = root  # 初始化根节点索引为最大值索引
    left = 2 * root + 1  # 左子节点索引
    right = 2 * root + 2  # 右子节点索引

    # 如果左子节点存在且大于根节点，则更新最大值索引
    if left < n and arr[left] > arr[largest]:
        largest = left

    # 如果右子节点存在且大于根节点，则更新最大值索引
    if right < n and arr[right] > arr[largest]:
        largest = right

    # 如果最大值索引不等于根节点索引，则交换根节点与最大值节点的值，并递归调整堆
    if largest != root:
        arr[root], arr[largest] = arr[largest], arr[root]
        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[0], arr[i] = arr[i], arr[0]  # 将当前根节点（最大值）与最后一个节点交换位置
        heapify(arr, i, 0)  # 调整堆，使剩余元素继续保持最大堆的性质

# 测试堆排序算法
arr = [12, 11, 13, 5, 6, 7]
print("原始数组：", arr)

heapSort(arr)
print("排序后的数组：", arr)

这段代码首先定义了两个函数：heapify 用于调整堆，使其满足堆的性质，heapSort 用于执行堆排序。然后通过 heapSort 函数对输入数组进行排序，并输出结果。

​

​