我是 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)
最佳答案
heapify 函数中有两个错误:
第二个分支不应该是
elif，而是if，因为即使左 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 - Python 中的 Heapsort 不排序，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/56912457/