数组下标从1开始的Heap sort（堆排序）代码IndexError报错排查

错误原因 #

• Python原生列表默认从下标0开始索引，你直接基于下标从1开始的规则编写代码，没有给原列表预留0下标占位位。你给出的测试列表长度为10，最大有效索引是9，代码执行时会访问list[10]，直接触发越界错误。
• maxHeapify函数中判断左右子节点大小误用while循环，此处仅需单次判断选出最大值节点即可，使用if更符合逻辑规范。
• 排序完成后如果直接遍历整个列表输出，会打印0下标位置的占位无效值，输出时需要从下标1开始遍历。

修正后可运行代码 #

# 堆化以i为根的子树
def maxHeapify(list, heapSize, i):
    largest = i
    leftChild = 2 * i 
    rightChild = 2 * i + 1
    if leftChild < heapSize and list[largest] < list[leftChild]:
        largest = leftChild
    if rightChild < heapSize and list[largest] < list[rightChild]:
        largest = rightChild
    if largest != i:
        list[i], list[largest] = list[largest], list[i]
        maxHeapify(list, heapSize, largest)

def heapSort(list):
    heapSize = len(list)
    # 构建大顶堆
    for i in range(heapSize//2, 0, -1):
        maxHeapify(list, heapSize, i)
    # 逐个提取堆顶元素完成排序
    for i in range(heapSize-1, 1, -1):
        list[i], list[1] = list[1], list[i]
        maxHeapify(list, i, 1)

# 列表首位加None作为占位，使用1~10下标存储元素
list = [None, 4, 1, 3, 2, 16, 9, 10, 14, 8, 7]
heapSort(list)
print("Sorted array is: ")
# 从下标1开始输出有效排序结果
for i in range(1, len(list)):
    print(list[i], end=" ")

运行输出 #

Sorted array is: 
1 2 3 4 7 8 9 10 14 16 

内容的提问来源于stack exchange，提问作者Sudipta Bhatta