Python实现HeapSort排序异常问题求助

你实现的堆排序失败核心原因是原算法基于1索引数组设计，但Python列表采用0索引，直接转写时未做适配，导致所有索引操作错位，最终排序错误。

具体错误点及修复方案 #

1. 初始参数与堆大小设置错误 #

原代码中n = len(A) - 1是错误的，这里的n应该是数组的总元素个数（即len(A)），因为堆的大小等于元素总数。同时makeheap中设置H.heapsize = n时，n必须是元素个数而非索引上限。

2. shiftdown函数的索引逻辑错误 #

原算法的左右孩子计算公式是针对1索引的（左孩子2*parent，右孩子2*parent+1），Python 0索引下应改为：

• 左孩子：2*i + 1
• 右孩子：2*i + 2
  同时判断右孩子是否存在的条件也需要调整，避免越界。

3. makeheap的起始节点错误 #

原算法从n//2（1索引的中间父节点）开始下沉，对应0索引应从(n//2)-1开始，因为0索引的中间父节点位置比1索引小1。

4. root函数的根节点位置错误 #

原代码取H.S[1]作为根节点，0索引下根节点在H.S[0]，交换元素时也需对应调整为最后一个有效元素（H.S[H.heapsize-1]）。

5. removekeys函数的赋值位置错误 #

原算法从1索引的n位置开始存放最大元素，0索引下应从n-1位置开始，依次向前填充，确保最大元素放到数组末尾。

修复后的完整代码 #

class Heap:
    def __init__(self, S, heapsize):
        self.S = S
        self.heapsize = heapsize


def shiftdown(H, i):
    siftkey = H.S[i]
    parent = i
    spotfound = False

    # 0索引下，左孩子是2*i+1，右孩子是2*i+2
    while (2 * parent + 1 < H.heapsize and not spotfound):
        # 判断右孩子是否存在且更大
        if (2 * parent + 2 < H.heapsize and H.S[2 * parent + 1] < H.S[2 * parent + 2]):
            largerchild = 2 * parent + 2
        else:
            largerchild = 2 * parent + 1

        if siftkey < H.S[largerchild]:
            H.S[parent] = H.S[largerchild]
            parent = largerchild
        else:
            spotfound = True

    H.S[parent] = siftkey


def makeheap(n, H):
    # 0索引下，起始父节点为(n//2)-1
    i = (n // 2) - 1
    H.heapsize = n
    while i >= 0:
        shiftdown(H, i)
        i -= 1


def root(H):
    # 0索引下根节点在位置0
    keytype = H.S[0]
    # 交换根节点与最后一个有效元素
    H.S[0] = H.S[H.heapsize - 1]
    H.heapsize -= 1
    shiftdown(H, 0)
    return keytype


def removekeys(n, H, A):
    # 从数组末尾开始填充最大元素
    i = n - 1
    while i >= 0:
        A[i] = root(H)
        i -= 1


def HeapSort(n, H):
    makeheap(n, H)
    removekeys(n, H, H.S)


if __name__ == '__main__':
    A = [30, 25, 20, 18, 12, 19, 17, 16, 14, 11]
    n = len(A)  # n为元素总个数

    H = Heap(A, n)
    print("初始堆大小:", H.heapsize)
    print("初始数组:", A)
    HeapSort(n, H)

    print("排序后数组:", H.S)

运行结果 #

执行后输出：

初始堆大小: 10
初始数组: [30, 25, 20, 18, 12, 19, 17, 16, 14, 11]
排序后数组: [11, 12, 14, 16, 17, 18, 19, 20, 25, 30]

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