插入一個列表，二叉樹

Question

我有一個這樣的名單：

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) 

Answer 1

我建議創建的每個元組對象，並使用與heapq模塊的對象列表。這樣你就可以控制排序順序並將最小堆變成最大堆。您也可以獨立訪問前元組元素屬性：

import heapq 

class Item(object): 
    def __init__(self, letter, value): 
     self.letter = letter 
     self.value = value 

    def __repr__(self): 
     return "Item({0}, {1})".format(self.letter, self.value) 

    def __le__(self, other): 
     # This is where you control whether it's a min heap or a max heap, 
     # and also what you want to sort on: value, letter or both. 
     return self.value > other.value 

items = [Item(*x) for x in a] 
heapq.heapify(items) 

編輯：改變<到>。