0
我有一個這樣的名單:插入一個列表,二叉樹
a=[(("x",0.312),("e",0.0232),("f",0.245),("a",0.1322))]
,現在我想將它插入到最大堆樹和每個節點必須有兩個值,例如,:(「X」 ,0.312),我可以分別得到兩個值。我知道如何實現Max Heap。我需要如何處理插入功能的幫助。 如果它更容易,它可以是二叉樹。由於
class Heap:
def __init__(self):
self.heap = list()
#return the size of the tree
def size(self):
return len(self.heap)
def isLeaf(self, index):
#returns true if the index refers to a leaf, false otherwise
return self.size() < 2 * index + 2
def parent(self, index):
#returns the parent of the node at index
return(index - 1) // 2
def leftChild(self, index):
#returns the index of the left child of a node
return 2 * index + 1
def rightChild(self, index):
#returns the index of the right child of a node
return 2 * index + 2
def add(self, value):
#add a given value to the heap
#append the value to the list
#shift the element into the correct position
self.heap.append(value)
index= self.size()-1
while self.parent(index) >=0 and self.heap[index] < self.heap[self.parent(index)]:
swap= self.heap[index]
self.heap[index]=self.heap[self.parent(index)]
self.heap[self.parent(index)]=swap
index = self.parent(index)
你看過[heapq](http://docs.python.org/2/library/heapq.html)模塊嗎? – 2013-04-25 06:50:32
@TommyNgo這是一個練習,還是您會接受建議爲此創建的模塊的答案? – jamylak 2013-04-25 07:00:33