插入一个列表，二叉树

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) 

编辑：改变<到>。