堆排序實作Python

我在 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]。該實作基于《演算法基礎：那不勒斯》，理查德第五版一書中的演算法 7.5，我嘗試直接轉換為 python。下面是投手。

任何的意見都將會有幫助！

書中的演算法如下所示：

我試圖通過筆和紙上的演算法找到打嗝發生的位置，但似乎仍然無法弄清楚......

uj5u.com熱心網友回復：

有幾個問題：

• 首先，該演算法宣告“S is indexed from 1 to N”。這不是 Python 串列的索引方式，因為它們從索引 0 開始。所以要么你必須翻譯代碼，以便所有索引都減少一個，或者（可能作業量更少）你可以在索引 0 處添加一個虛擬值到你的 PythonS串列。然后資料可以從索引 1 開始。這也意味著在主程式中不能列印索引 0 處的值。

• 您在 中的第一個if條件中打錯了字shiftdown。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

uj5u.com熱心網友回復：

我嘗試了虛擬值，但它對我不起作用。我仍然以不正確的排序結束。因為使用 len(list) 會丟東西，所以我heapsize在 BuildMaxHeap 和 MaxHeapify 方法中創建了一個變數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)

標籤：Python算法排序堆排序

上一篇：素數分解的除數數

下一篇：理解Leetcode1366的時間/空間復雜度