Python实现堆排序遇RecursionError：递归深度超出问题排查

你的代码里有好几处问题导致了RecursionError以及其他潜在错误，逐个梳理：

• 无限递归触发栈溢出
  _max_heapify函数里，当largest == i时（当前节点已是最大值，无需交换），你没有终止递归，而是直接继续调用自身，这会导致无限递归，最终触发递归深度超限错误。必须仅在largest != i时才执行递归。

• 变量名大小写不匹配
  Python是大小写敏感的，代码里多处混用大写I和小写i：

  • heap_sort里的_max_heapify(A,heap_size, I)
  • _build_max_heap里的_max_heapify(A,heap_size, I)
  • _left函数参数写的是I，但内部用的是i
    这些会直接引发NameError或错误的索引计算。

• range函数使用错误

  • heap_sort里的for i in range(heap_size // 2, -1)：默认步长为1时，起始值大于结束值不会生成任何循环元素。堆排序正确的遍历范围应该是从最后一个元素倒序到索引1，写法为range(heap_size-1, 0, -1)。
  • _build_max_heap里的for i in range(heap_size // 2)：构建最大堆需要从最后一个非叶子节点开始倒序遍历，也就是heap_size//2 -1到0，正确写法是range(heap_size//2 -1, -1, -1)。

• _left函数参数定义错误
  _left函数参数写的是大写I，但内部用的是小写i，会导致未定义变量错误，需将参数改为小写i。

修正后的完整代码 #

def heap_sort(A):
    heap_size = _build_max_heap(A)
    # 从最后一个元素倒序遍历到索引1
    for i in range(heap_size - 1, 0, -1):
        # 交换堆顶和当前最后一个元素
        A[0], A[i] = A[i], A[0]
        heap_size -= 1
        # 对新的堆顶进行堆化
        _max_heapify(A, heap_size, 0)

def _build_max_heap(A):
    heap_size = len(A)
    # 从最后一个非叶子节点倒序遍历堆化
    for i in range(heap_size // 2 - 1, -1, -1):
        _max_heapify(A, heap_size, i)
    return heap_size

def _left(i):
    return (2 * i) + 1

def _right(i):
    return (2 * i) + 2

def _max_heapify(A, heap_size, i):
    l = _left(i)
    r = _right(i)
    largest = i
    # 找左子节点和当前节点的较大值
    if l < heap_size and A[l] > A[largest]:
        largest = l
    # 找右子节点和当前最大值的较大值
    if r < heap_size and A[r] > A[largest]:
        largest = r
    # 如果最大值不是当前节点，交换后递归堆化
    if largest != i:
        A[i], A[largest] = A[largest], A[i]
        _max_heapify(A, heap_size, largest)

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