堆排序没有工作的python

Question

参照MIT的开放课程软件自选课程第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

build_max_heap保证是正确的，因为我用pythons库检查了它。

然而，heap_sort似乎不能正常工作，

test_array = [1,5,3,6,49,2,4,5,6]
heap_sort(test_array)
print(test_array) # --> [6,5,5,4,3,49,6,2,1]

完全困惑在这里，我交叉检查了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，尽管它应该是A。

第二，在build_max_heap中使用变量最大值意味着，最大变量是一个全局变量声明，而您的问题中没有提供它，或者您打算使用i。我认为这是第二种情况，而且由于我有一个基于您提供的代码的工作heap_sort，所以我认为我的假设是正确的。

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

最后，您最重要的错误是，您一直在传递整个数组，并使用一个不会减少的数组长度。(即，始终是test_array的初始长度)您使用的算法查找给定数组的最大元素，并将其排除在结构的其余部分之外。这样，您就有了一个数组，该数组的大小不断减小，同时将其最大元素发送到末尾。(即仅超出它的可及范围/长度)，但是，由于您从未缩小数组的大小，而且它的长度被连续计算为len(test_array)，因此它永远不会像预期的那样工作。

有两种方法可以解决你的问题。选项1将在max_heapify中传递给heap_sort中的一个较短版本的A。具体来说，您应该在循环的每次迭代中传递A:curr_heap_size。此方法可以工作，但并不是真正的空间效率，因为您每次都会创建一个新的列表。相反，您可以将curr_heap_size作为参数传递给函数build_max_heap和max_heapify，并假定这是长度。(即相对于len(A))

下面是一个基于代码的工作heap_sort实现。我所做的就是改正上面列出的错误。

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