Python 中的 Heapsort 不排序

Question

我是 python 的新手，我正在尝试从我的 C++ implementation 中实现堆排序。此代码无法对输入进行排序。

我已经写了另一个程序来测试函数build_max_heap，这个函数无法建立最大堆。

def max_heapify(thelist, lst_size, idx):
    largest = idx
    left_child = (2 * idx) + 1
    right_child = (2 * idx) + 2

    if left_child < lst_size and thelist[left_child] > thelist[largest]:
        largest = left_child

    elif right_child < len(thelist) and thelist[right_child] > thelist[largest]:
        largest = right_child

    if largest != idx:
        thelist[idx], thelist[largest] = thelist[largest], thelist[idx]
        max_heapify(thelist, lst_size, largest)

def build_max_heap(thelist, lst_size):
    for curr_idx in range(lst_size // 2 - 1, -1, -1):
        max_heapify(thelist, lst_size, curr_idx)

def heap_sort(thelist):
    if len(thelist) == 0:
        print("Empty list!!")

    elif len(thelist) == 1:
        print("Only one element!!")

    else:
        build_max_heap(thelist, len(thelist))

        for curr_idx in range(len(thelist) -1, 0, -1):
            thelist[curr_idx], thelist[0] = thelist[0], thelist[curr_idx]
            max_heapify(thelist, curr_idx, 0)

Answer 1

您的 heapify 函数中有两个错误：

第二个分支不应该是 elif，而是 if，因为您需要 select 右边的 child，即使左边的child大于它的parent，但是当右边的child更大时。
你不想在那里使用 len(thelist)，因为你的函数应该依赖参数 lst_size。这是必需的，因为在 heap_sort 函数调用中，为该参数传递的值小于（并且必须）小于实际列表长度。

所以改变：

elif right_child < len(thelist) and thelist[right_child] > thelist[largest]:

至：

if right_child < lst_size and thelist[right_child] > thelist[largest]:

Python 中的 Heapsort 不排序

Heapsort in Python does not sorting

python

python-3.x

algorithm

heapsort