使用 max/min 堆进行堆排序和反向堆排序

Question

我只是想检查一下我是否理解教授和在线资源所说的内容。

对于 heapSort 算法，第一个元素的索引从 0 开始。

对于最大堆，如果子级大于父级，向下渗透应该将最大子级与其父级交换，所以类似（这是一个赋值，所以我尝试 post 作为小代码尽可能）：

def percolateDownMaxHeap( array, hole, length):
    while hole * 2 < size - 1:
        left = 2*hole + 1
        right = left + 1

        max = left

        if (left < size - 1) and (array[right] > array[left]):
            max = right

        if (array[max] > array[hole]):
            swap(array, hole, max)

        else:
            break

        hole = max

所以最后，最大元素应该在索引 0 处。

如果这是正确的，我不明白的是 heapSort 实现：

def heapSort(array):
    i = len(array) / 2
    while i >= 0:
        percolateDownMaxHeap( array, i, len(array))
        i -= 1

    i = len(array) - 1

    while i > 0:
        swap( array, 0, i );
        percolateDownMaxHeap( array, i, len(array))
        i -= 1

在最大堆中向下渗透不是应该将最大元素放在索引 0 处吗？在这种情况下，为什么不在最小堆上使用 percolate down？代码有效，但我不确定我是否做对了，或者我是否实现了最大堆而不是最小堆

谢谢

Answer 1

Isn't percolate down in a max heap supposed to put the largest element at index 0?

确实如此。然后你的代码将它交换到堆之外，因此每次连续交换都会将下一个最大的元素放在它所属的位置。

In this case why not use percolate down on a min heap?

这将使最小元素位于正确的位置，但堆仍然需要数组中的那个位置，因此不清楚如何处理下一个元素。

使用 max/min 堆进行堆排序和反向堆排序

heap sort and reverse heap sort with max/min heap

algorithm

sorting

heap

heapsort