python - 返回 lambda 节点 < 节点

Question

将节点放入最低优先级队列时，我收到此编译器错误。

TypeError: '<' not supported between instances of 'Node' and 'Node'

这是失败的地方

from queue import PriorityQueue

def huffman(text):
    A = frequency(text) # returns a dictionary {(frequency, character),...}
    q = PriorityQueue()
    heap = build_min_heap(A) # builds min heap 
    while heap:
        temp = pop_heap(heap) # format (frequency, character)
---->   q.put(Node(temp[1],temp[0],None,None))
        # Node(character, frequency, left child, right child)

def min_heapify(A, i, key=lambda a: a):
    lefti = 2 * i + 1
    righti = 2 * i + 2
    heap_size = len(A)
--->if lefti < heap_size and key(A[lefti]) < key(A[i]):

    /anaconda3/lib/python3.6/queue.py in put(self, item, block, timeout)
    141                             raise Full
    142                         self.not_full.wait(remaining)
--> 143             self._put(item)
    144             self.unfinished_tasks += 1
    145             self.not_empty.notify()

    /anaconda3/lib/python3.6/queue.py in _put(self, item)
    225 
    226     def _put(self, item):
--> 227         heappush(self.queue, item)
    228 
    229     def _get(self):

我通过向 Node 类添加“lt”函数找到了一种解决方法。

def __lt__(self, other):
    return self.frequency < other.frequency

但是，是否有另一种方法可以使用 lambda 表达式或以某种方式修改最小优先级队列来解决此问题？

也许是一个关键功能？我了解 key(value) 在做什么，但我不知道如何将其解释为 Node.js。我尝试了以下类似的方法，但没有奏效。

def key(item):
    if instanceof(item, Node):
        return item.frequency

另外要注意的是，堆函数也处理 int 值和其他类型。这是在我将节点传递到堆/队列的代码中的稍后部分。

注意：节点按频率排序。

这是我的节点类

class Node():

    def __init__(self, character=None, frequency=None, left=None, right=None):
        self.character = character
        self.frequency = frequency
        self.left = left
        self.right = right

    def isLeaf(self):
        return self.left is None and self.right is None

    def __lt__(self, other):
        return self.frequency < other.frequency

    def __repr__(self):
        return 'Node({}, {}, {}, {})'.format(self.character,
                                         self.frequency,
                                         self.left, self.right)

def min_heapify(A, i, key=lambda a: a):
    lefti = 2 * i + 1
    righti = 2 * i + 2
    heap_size = len(A)
    if lefti < heap_size and key(A[lefti]) < key(A[i]):
        smallesti = lefti
    else:
        smallesti = i
    if righti < heap_size and key(A[righti]) < key(A[smallesti]):
        smallesti = righti
    if smallesti != i:
        A[i], A[smallesti] = A[smallesti], A[i]
        min_heapify(A, smallesti, key)

def build_min_heap(A, key=lambda a: a):
    for i in range(len(A) // 2 - 1, -1, -1):
        swaps = min_heapify(A, i, key)
    return A

最后一句话，我知道“lt”在 Node 类中有效，但我试图找出另一个不涉及修改 Node 类的解决方案，因为其他站点有评论说使用 lambda 表达式（例如key 函数应该将参数中存储的频率返回给 key，它应该是一个 Node。；我们是否需要编写 key 函数？是的。它可以是一个简单的 lambda 表达式。）但他们在如何实现这一点上很模糊。

标签： pythonheapnodespriority-queue