python - 为什么我的堆排序不起作用？

Question

我有这个 python Heapsort-Code 是从网上的伪代码制作的。

但它给出了错误的结果。

def heapSortUp(a):          
    heapifyUp(a, len(a))

    end = len(a)-1
    while end > 0:
        a[end], a[0] = a[0], a[end]
        end -= 1
        siftUp(a, 0, end)
    return a

def heapifyUp(a, count):
    end = 1

    while end < count:
        siftUp(a, 0, end)
        end += 1

def siftUp(a, start, end):
    child = end

    while child > start:
        parent = int(math.floor((child-1)/2))       # floor = abrunden

        if a[parent] < a[child]:
            a[parent], a[child] = a[child], a[parent]
            child = parent
        else:
            return

我特别想用 siftUP 版本。

通过计算 print heapSortUp([1,5,4,2,9,8,7])它返回:[8, 7, 9, 2, 1, 4, 5, 7, 5]

Answer 1

问题是你需要在 heapSortUp(a) 中向下而不是向上筛选

def heapSortUp(a):          
    heapifyUp(a, len(a))

    end = len(a)-1
    while end > 0:
        a[end], a[0] = a[0], a[end]
        end -= 1
        siftDown(a, 0, end)
    return a

您需要向下筛选的原因是向上筛选会使堆无效。这可以用一个简单的例子来说明。

取一个堆 4,3,2,1。在这种排序的一次迭代之后，您将在末尾放置 4 个，在前面放置 1 个。所以堆看起来像一棵树

 1
3 2

然而，当您向上筛选时，您交换了 1 和 2。这意味着 2 比 3 具有更高的优先级。如果您继续进行排序(如所写)，您将排列数组 1,3,2,4

要获得实际的排序，您需要筛选一个，以便堆看起来像第一次迭代后的样子。

 3
1 2

我将 siftDown 的实现留给你。