堆排序和使用最大/最小堆的反向堆排序

Question

我只是想看看我是否理解教授和在线资源所说的话。

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

对于最大堆，如果子堆大于父堆，则percolate down应将最大子堆与其父堆交换，例如（这是用于赋值，因此我尝试发布尽可能少的代码）：

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处吗？在这种情况下，为什么不在最小堆上使用渗滤液呢？代码可以工作，但我不确定是否正确，或者是否实现了最大堆而不是最小堆

谢谢

Answer 1

在最大堆中渗透不是应该把最大的元素放在索引0吗？

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

在这种情况下，为什么不在最小堆上使用渗滤？

这将使min元素处于正确的位置，但堆在数组中仍然需要该位置，因此不清楚下一个元素应该做什么。