我有这个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版本.

通过计算打印heapSortUp([1,5,4,2,9,8,7])
它返回：[8、7、9、2、1、4、5、7、5]

解决方法:

问题是,您需要筛选不堆在upSortUp(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实现留给您.