Heap排序实现Python

Question

在python中实现HeapSort有一些问题。输入序列没有正确排序..。这个

实现如下所示：

class Heap:
  def __init__(self, S, heapsize):
    self.S = S
    self.heapsize = heapsize



def shiftdown(H, i):
    
    siftkey = H.S[i]
    parent = i 
    spotfound = False

    

    while (2*parent <= H.heapsize and not spotfound):
        if (2*parent < H.heapsize and H.S[2*parent] < H.S[2*parent - 1]):
            largerchild =  2*parent + 1
        else:
            largerchild =  2*parent

        if(siftkey < H.S[largerchild]):
            H.S[parent] = H.S[largerchild]
            parent = largerchild
        else:
            spotfound = True
        
    H.S[parent] = siftkey
    



def makeheap(n, H):
    i = int(n/2)
    
    H.heapsize = n
    while i >= 1:
        shiftdown(H, i)
        i -= 1


def root(H):
    keytype = H.S[1]
    H.S[1] = H.S[H.heapsize]
    H.heapsize = H.heapsize - 1
    shiftdown(H, 1)
    return keytype

def removekeys(n, H ,A):
    
    i = n
    while(i >= 1):
        A[i] = root(H)
        i -= 1

        


def HeapSort(n, H):
    makeheap(n, H)
    removekeys(n, H, H.S)
    



if __name__ == '__main__':
    A = [30, 25, 20, 18, 12, 19, 17, 16, 14, 11]
    n = len(A) - 1

    H = Heap(A, n)
    print(H.heapsize)
    print(A)
    HeapSort(n, H)

    
    print(H.S)

输入A导致输出30、11、16、12、14、17、18、19、20、25。该实现基于“算法基础”(：Neapolitan，Richard第五版)中的算法7.5，我尝试将其直接转换为python。在下面加一些沥青。

任何建议都是有帮助的！

书中的算法如下：

​

​

​

​

​

​

我试着在纸和笔上找出打嗝的地方，但似乎还是找不出.

Answer 1

有几个问题：

• 首先指出，"S是从1到N的索引“。这不是Python列表的索引方式，因为它们从索引0开始。因此，要么您必须转换代码，以便使所有索引都少一个，要么(可能更少的工作量)您可以在索引0处向您的Python添加一个虚拟值。然后数据可以从索引1开始，这也意味着在主程序中，您不能在索引0.

处打印值。

• 您在shiftdown中的第一个if条件中输入了一个错误。您应该将H.S[2*parent + 1]

中的H.S[2*parent - 1]更正为

• 主程序不应该从len(A)中减去一个--这是没有意义的。长度真的是len(A).

以下是更正后的脚本：

class Heap:
    def __init__(self, S, heapsize):
        self.S = [None] + S   # The source aglorithm has no 0 index
        self.heapsize = heapsize

def shiftdown(H, i):
    siftkey = H.S[i]
    parent = i 
    spotfound = False
    while (2*parent <= H.heapsize and not spotfound):
        # bug fix
        if (2*parent < H.heapsize and H.S[2*parent] < H.S[2*parent + 1]):
            largerchild =  2*parent + 1
        else:
            largerchild =  2*parent
        if(siftkey < H.S[largerchild]):
            H.S[parent] = H.S[largerchild]
            parent = largerchild
        else:
            spotfound = True
    H.S[parent] = siftkey
    
def makeheap(n, H):
    i = int(n/2)
    H.heapsize = n
    while i >= 1:
        shiftdown(H, i)
        i -= 1

def root(H):
    keytype = H.S[1]
    H.S[1] = H.S[H.heapsize]
    H.heapsize = H.heapsize - 1
    shiftdown(H, 1)
    return keytype

def removekeys(n, H ,A):    
    i = n
    while(i >= 1):
        A[i] = root(H)
        i -= 1

def HeapSort(n, H):
    makeheap(n, H)
    removekeys(n, H, H.S)


A = [30, 25, 20, 18, 12, 19, 17, 16, 14, 11]
n = len(A) # Don't subtract one here!
H = Heap(A, n)
print(H.heapsize)
print(A)
HeapSort(n, H)
print(H.S[1:])  # Must skip index 0

Answer 2

我试过假人的价值，但对我没有用。我的结果还是不对。由于使用len(list)抛出了一些东西，所以我在BuildMaxHeap和MaxHeapify方法heapsize = len(list3)-1中创建了一个变量heapsize = len(list3)-1，然后在if语句中使用了这个变量。

if l <=heapsize and (list3[l]) > list3[i]:
        largest = l
    else:
         largest = i
    if r <= heapsize and (list3[r]) >list3[largest]:
        largest = r

我不知道这是否也会导致问题，但在我的BuildMaxHeap中，我使用了for语句，并必须倒计时到负1，以确保它不会漏掉第一个元素。

for i in range (int(heapsize/2),-1,-1):
        MaxHeapify(list3, i)