python - 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 函数中有两个错误:

1. 第二个分支不应该是 elif，而是 if，因为即使左 child 是大于其父级，但当右子级甚至更大时。

2. 您不想在那里使用 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]: