在Python中構建MIN-HEAP

Question

我必須在Python中構建完整的MIN-HEAP實現，而不使用內置的堆函數。

所以我有父母，左子女和右子女的定義，這需要在考慮從0蟒蛇號碼列表元素：

from random import randint 
import math 

def parent(i): 
    x = int(l.index(l[i])) #########3 
    y = int(math.floor(x/2)) 
    return y-1 

def lchild(i): 
    x = int(l.index(l[i])) 
    y = int(math.floor(x*2)) 
    return y-1 

def rchild(i): 
    x = int(l.index(l[i])) 
    y = int(math.floor(x*2 + 1)) 
    return y-1 

那麼我的生成代碼（僞）的一部分隨機列表我到列表升：

l = [] 
dl = int(input) 

for i in range (0, dl): 
    x = int(randint(1,100)) 
    l.append(x)    

與直到此時一切正常良好。然後我有一個函數bkop，使表l成爲一個小堆。

def bkop(l): 
     j = 0 
     for i in range(0, len(l)): 
       if int(l[i]) < int(parent(l[i])): #########2 
         l[i], l[parent(i)] = l[parent(i)], l[i] 
         j = j+1 
       if j != 0: 
         bkop(l) 

那麼我想運行一個程序，並查看結果：一個錯誤列表索引

bkop(l) #########1 
print l 

程序崩潰了的指向3線範圍，我已標記與#########。我從一個月前開始寫這篇文章，我很確定，那時候，那個父母lchild和rchild工作。你知道嗎，怎麼了？

EDIT1： 好的，所以我修復了父/子/兒的定義。我檢查過，他們返回正確的值。這裏是代碼：

def parent(i): 
    x = i + 1 
    y = x//2 
    return y-1 

def lchild(i): 
    x = i + 1 
    y = x*2 
    return y-1 

def rchild(i): 
    x = i + 1 
    y = x*2 + 1 
    return y-1 

生成隨機列表的函數幾乎完好無損。然後，我有這個bkop函數（這使得列表中的最小堆不在列表中）。我在目的之前和之後使用打印，以確定它是否有效......但事實並非如此。它兩次返回相同的列表，沒有編譯錯誤或任何東西。任何想法如何解決它？

print(l) 
def bkop(l): 
     j = 0 
     for i in range(0, len(l)): 
       if l[i] < parent(i): 
         l[i], l[parent(i)] = l[parent(i)], l[i] 
         j = j+1 
       if j != 0: 
         bkop(l) 
bkop(l) 
print l 

EDIT2： 好了，我已經固定bkop爲你推薦：

print bkop(l) 
def bkop(l): 
     j = 0 
     for i in range(1, len(l)): 
       if l[i] < l[parent(i)]: 
         l[i], l[parent(i)] = l[parent(i)], l[i] 
         j = j+1 
       if j != 0: 
         bkop(l) 
bkop(l) 
print bkop(l) 

但是當我運行它，我得到這個第一個隨機生成的表格（如我應該），和而不是最小堆表，我得到無值，如下圖所示：

[34, 9, 94, 69, 77, 33, 56] 
None 

任何IDE如？也許我應該以另一種方式去做，而不是將l [i]與父母進行比較，但是l [i]是左右兒童？

Answer 1

所以我已經得到了Wombatz的幫助（非常感謝！）。這是對未來用戶的工作代碼：

from random import randint 

def parent(i): 
    x = i + 1 
    y = x//2 
    return y-1 

def lchild(i): 
    x = i + 1 
    y = x*2 
    return y-1 

def rchild(i): 
    x = i + 1 
    y = x*2 + 1 
    return y-1 



l = [] 
dl = int(input()) 

for i in range (0, dl): 
    x = int(randint(1,100)) 
    l.append(x) 

print l 
def bkop(l): 
     j = 0 
     for i in range(1, len(l)): 
       if l[i] < l[parent(i)]: 
         l[i], l[parent(i)] = l[parent(i)], l[i] 
         j = j+1 
       if j != 0: 
         bkop(l) 
bkop(l) 
print l 

運行時，我已經把13輸入列表長度和我已經得到了結果：

13 
[30, 62, 9, 100, 75, 73, 57, 82, 2, 76, 2, 50, 41] #before heapify 
[2, 2, 30, 62, 9, 41, 57, 100, 82, 76, 75, 73, 50] #after heapify 

Answer 2

起初：有一個問題，您parent，lchild和rchild功能：

• l[index]獲取給定的索引值。

• l.index(...)獲得給定值的索引。

您正試圖獲取特定索引值的索引。這就像x + 1 - 1。如果您的項目是唯一的，那麼計算出的索引將始終與您開始使用的索引相同。當有重複時，你的函數將計算該索引值第一次出現的父，左和右子。 這可能不是你想要的。因此請將x設置爲i或完全刪除x。

實際問題如下：

你parent，lchild和rchild功能desined到上index工作，但你在指數i合格l值的函數：parent(l[i])

由於列表中的值可能遠高於您正在獲取的可能的索引範圍列表索引超出範圍。您可能想要直接傳遞索引。

此外：

parent，lchild和rchild返回不正確的值。測試這些功能沒有所有其他的東西！

我想結果應該是這樣的：

• parent(1) == parent(2) == 0
• lchild(0) == 1
• rchild(0) == 2

你定義返回的值不同。

一些小事情：

• 所有這些隨機int的轉換都是無用的。鑄造int到int什麼都不做。唯一真正需要演員陣容的是：``dl = int（input）`
• int(math.floor(x/2))。使用整數除法x // 2代替
• int(math.floor(x*2))。整數次數2是一個整數。不需要floor它。

編輯 兩件事情是不對您的bkop功能。

• l[i] < parent(i)您將該值與索引進行比較。我想你想要將i的價值競爭到它的父值，而不是父指數。
• 對於i == 0您將索引0的值與parent(0) == -1的值進行比較。這包裹在列表中，可能不是你想要的。由於索引0沒有父母，因此您不應該嘗試將其與父母進行比較。

EDIT2

bkop不會返回列表中，但修改它就地。最後只需print(l)。您會看到原始列表已被修改。