0

我有一个这样的列表：

a=[(("x",0.312),("e",0.0232),("f",0.245),("a",0.1322))]

现在我想将它插入到最大堆树中，并且每个节点都必须具有两个值，例如：（“x”，0.312），我可以分别获得这两个值。我知道如何实现最大堆。我需要有关如何处理插入功能的帮助。如果它更容易，它可以是二叉树。谢谢

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)
4

1 回答 1

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)

编辑：更改<为>.

于 2013-04-25T06:59:18.420 回答