堆排序不工作 python

Question

参考MIT公开课ware algo course chapter 4，根据给出的伪代码创建堆排序：

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 heapq库检查过。

但是，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[0].

其次，您在 build_max_heap 中对变量 largest 的使用意味着 largest 是您在问题中未提供的全局变量声明，或者您打算改用 i。我假设这是第二种情况，并且由于我有一个基于您提供的代码的工作 heap_sort，我认为我的假设是正确的。

第三，在 max_heapify 中，您将 largest 初始化为 l，尽管您应该将其初始化为 i。我相信你会发现这是一个微不足道的错误，因为在同一个函数的更深处，你显然期望 largest 的值等于 i 的值。

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

有两种方法可以解决您的问题。选项 1 传递给 max_heapify heap_sort 中 A 的较短版本。具体来说，您应该在循环的每次迭代中传递 A[:curr_heap_size] 。这种方法可行，但实际上 space 效率不高，因为您每次都要创建一个新列表。相反，您可以将 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

堆排序不工作 python

Heap sort not working python

python

sorting

heapsort