heapify O（n）算法

我正在編寫一個O（n）算法的'heapifying'在Python中的列表。我不明白爲什麼它不起作用。heapify O（n）算法

def func(l): 
    size=len(l) 
    for root in range((size//2)-1,-1,-1): 
     child = 2*root+1 #parent of child is target 
     while(child<size): 
      #l[child] should be smaller sibling 
      if child<size-1 and l[child]>l[child+1]: 
       child+=1 
      #can we put l[root] in l[child//2]? 
      if l[root]<=l[child]: 
       break #yes 
      #no 
      l[child//2]=l[child]#move child up 
      child=2*child+1#move down a level 
     l[child//2]=l[root] 
    return l

來源

2014-04-16 Faustus

小號要根的孩子在正確的位置。 2 * root和2 * root + 1？ –

@MicahSmith：如果這些索引是基於零的，就像在Python中一樣。 'root'的孩子是'2 * root + 1'和'2 * root + 2'。 – Blckknght

@Blckknght聽起來不錯。在我的DS課程中，我們學會了將root放入索引1並將索引0留空。（要同時允許以上模式並在heapify期間用作佔位符。） –

你的函數有兩個問題。

第一個很容易掌握。您正在使用錯誤的計算來查找child索引的父級。而不是child // 2，你應該使用(child - 1) // 2。這導致你將一些價值觀轉移到了錯誤的地方。

第二個問題有點微妙。如果l[root]比其子中的一個大，則當前正在用該子代覆蓋它，因此當您嘗試將其插入到列表中的其他位置時，原始值將不再可用。也許你應該在for循環的頂部保存l[root]，然後使用保存的值的任何您目前檢查l[root]的代碼（if的while循環內，並且其結束後的最終分配後的時間。

這裏的代碼的固定版本，意見指出我所做的更改：

def func(l): 
    size=len(l) 
    for root in range((size//2)-1,-1,-1): 
     root_val = l[root]    # save root value 
     child = 2*root+1 
     while(child<size): 
      if child<size-1 and l[child]>l[child+1]: 
       child+=1 
      if root_val<=l[child]:  # compare against saved root value 
       break 
      l[(child-1)//2]=l[child] # find child's parent's index correctly 
      child=2*child+1 
     l[(child-1)//2]=root_val  # here too, and assign saved root value 
    return l

來源

2014-04-16 03:36:11 Blckknght

以上尼斯的解釋，這裏是一個小修改版：

# heapify in place 
def heapify(A): 
    # write your code here 
    for root in xrange(len(A)//2-1, -1, -1): 
     rootVal = A[root] 
     child = 2*root+1 
     while child < len(A): 
      if child+1 < len(A) and A[child] > A[child+1]: 
       child += 1 
      if rootVal <= A[child]: 
       break 
      A[child], A[(child-1)//2] = A[(child-1)//2], A[child] 
      child = child *2 + 1

來源

2015-09-21 09:46:11

heapify O（n）算法

回答

相關問題