堆排序无法工作python

Question

参考麻省理工学院的开放课程ware algo课程第4章，我根据给定的psuedocode创建了堆排序：

def heap_sort(A):
    build_max_heap(A)
    curr_heap_size = len(A)
    while curr_heap_size:
        A[0],A[curr_heap_size-1] = A[curr_heap_size-1],A
        curr_heap_size -= 1
        max_heapify(A,0)
    return A

构建最大堆保证是正确的，因为我用pythons heapq库检查了它。在

但是，heap_sort似乎无法正常工作

^{pr2}$

在这里完全被难住了，我用Heap sort Python implementation交叉检查，结果似乎是一样的。。。在

谢谢你的帮助，谢谢！在

编辑：max_heapify和build_max_heap的代码：

def max_heapify(A,i):
    heap_size = len(A)
    l,r = i*2+1,i*2+2
    largest = l
    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,largest)

def build_max_heap(A):
    array_size = len(A)
    for i in range(array_size // 2 ,-1,-1):
        max_heapify(A,largest)

Answer 1

您的代码中有一些错误使得重新生成案例和找到特定问题的解决方案变得更加困难，但是现在就这样。在

首先，您的代码在heap_sort函数中包含语法错误，特别是当您尝试交换a的第一个和最后一个元素时。在该赋值的右侧，第二个值是a，即使它应该是[0]。在

其次，在build_max_heap中使用变量maxists意味着maximust是您在问题中没有提供的全局变量声明，或者您打算使用i。我假设这是第二种情况，由于我有一个基于您提供的代码的有效堆排序，我认为我的假设是正确的。在

第三，在max_heapify中，您将maximust初始化为l，即使您应该用i初始化它。我相信您会发现这是一个小错误，因为在同一个函数下，您显然期望最大值的值等于i的值

最后，您最关键的错误是，您一直向下传递整个数组，并使用一个永远不会减少的数组长度（即，它总是test_数组的初始长度）。您使用的算法会找到给定数组的最大元素，并将其从结构的其余部分中排除。这样，数组的大小会不断减小，同时会将其最大的元素发送到末尾（即刚好超出的范围/长度），但是，由于数组的大小从未减小，并且其长度持续计算为len（test_array），因此它永远不会按预期工作。在

有两种方法可以解决您的问题。选项1将堆内排序的较短版本传递给max_heapify。具体来说，您应该在循环的每次迭代中传递一个[：curr_heap_size]。这个方法可以工作，但它并不是真正的节省空间，因为您每次都创建一个新列表。相反，您可以将curr_heap_size作为参数传递给函数build_max_heap和max_heapify，并假定其为长度。（即相对于len（A））

下面是一个基于您的代码的堆排序实现。我所做的就是修正上面列出的错误。在

def max_heapify(A, heap_size, i):
    l,r = i*2+1,i*2+2
    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)

def build_max_heap(A, array_size):
    for i in range(array_size // 2 ,-1,-1):
        max_heapify(A, array_size, i)

def heap_sort(A):
    curr_heap_size = len(A)
    build_max_heap(A, curr_heap_size)
    while curr_heap_size > 0:
        A[0], A[curr_heap_size-1] = A[curr_heap_size-1], A[0]
        curr_heap_size -= 1
        max_heapify(A, curr_heap_size, 0)
    return A