这是有效的HeapSort吗？

Question

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

在此之前，非常感谢您。

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()应该比较堆(树结构)中的Parent/Child的元素。它们在数组中的相对位置是

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

在数组的索引方面。这在您的实现中并不明显。

Answer 2

您所写的似乎是一个Selection Sort。

堆排序将数组排列成堆(最简单的二进制堆)，在堆中找到最小元素的时间是O(1)，删除最小元素的时间是O(log )，插入元素的时间也是O(log )。然后，它反复使用其中最小的元素来生成排序的顺序。