python - 这是有效的堆排序吗？

Question

在过去的 6 个小时里，我一直在阅读有关构建堆排序的教程和学术 Material 。我终于在 python 中原型(prototype)化了一些对整数列表进行排序的东西。但是，我不完全确定我的解决方案是否构成有效的堆排序。这是一个非常简单的解决方案，绝对可以改进，但我想知道它是否有效。令人困惑的是，每个人似乎都有自己“首选”的实现该算法的方式。

提前非常感谢。

def heapsort(array):
    array = heapify(array)
    array = insert(array, 9999)
    print(array)

def heapify(array):
    end = len(array)
    i = 0
    j = 0
    while i < end:
        while j < end:
            if array[i] > array[j]:
                array = swap(array, i, j)
            j += 1
        i += 1
        j = i
    return array

def insert(array, x):
    array.append(x)
    return heapify(array)


def swap(array, a, b):
    temp = array[a]
    array[a] = array[b]
    array[b] = temp
    return array

def main(array):
    heapsort(array)

if __name__ == '__main__':
    array = [3, 1, 2, 4, 6, 7, 9, 0]
    main(array)

Answer 1

您的 heapify() 应该比较堆(树结构)中的父/子元素。它们在数组中的相对位置是

ChildIndex = 2 * Parent Index + [0|1]  # two children per parent

就数组索引而言。这在您的实现中并不明显。