堆排序算法的实现步骤如下:
下面是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]