python - “<' not supported between instances of ' str”和 'Node'？

Question

我正在尝试实现霍夫曼编码算法，但由于优先级队列的比较，不断出现此错误。
我的代码:

class Node(object):
    def __init__(self, left=None, right=None):
        self.left = left
        self.right = right
    def children(self):
        return(self.left, self.right)
    def __lt__(self,other):
        return 0

def create_tree(count):
    print(count)
    priority = queue.PriorityQueue()
    for value in count:
        priority.put(value)
    while priority.qsize() > 1:
        one, two = priority.get(), priority.get()
        node = Node(one, two)
        priority.put((one[0]+two[0], node))
    return priority.get()

我曾多次尝试在 HuffmanNode 类中使用 _lt_，但最终总是无法将 'str' 与 'Node'、'int' 或 'tuple' 进行比较。我想知道是否可以做到这一点，如有任何建议，我们将不胜感激。

编辑:create_tree 的计数也是一个元组列表，如下所示:
[(1,'a'),(1,'b'),(2,'c')]

应该产生错误的代码:

[(1, 113), (1, 107), (1, 98), (1, 120), (1, 106), (1, 118), (1, 108), (1, 122), (1, 121), (1, 100), (1, 87), (1, 70), (1, 10), (2, 84), (2, 117), (2, 99), (2, 119), (2, 102), (2, 109), (2, 97), (2, 46), (3, 110), (3, 112), (4, 114), (4, 115), (4, 116), (4, 103), (5, 104), (5, 101), (7, 105), (8, 111), (18, 32)]

还意识到我更改了代码，因此它使用 ASCII 值而不是字符串，但无论是“int”还是“str”，我都会遇到相同的错误

Answer 1

这是直接从 PriorityQueue 的文档中提取的:

The lowest valued entries are retrieved first (the lowest valued entry is the one returned by sorted(list(entries))[0]). A typical pattern for entries is a tuple in the form: (priority_number, data).

If the data elements are not comparable, the data can be wrapped in a class that ignores the data item and only compares the priority number.

他们给出的示例代码是:

from dataclasses import dataclass, field
from typing import Any

@dataclass(order=True)
class PrioritizedItem:
    priority: int
    item: Any=field(compare=False)

使用您为 count = [(1, 'a'), (1, 'b'), (2, 'c')] 提供的示例:

def create_tree(count):
    print(count)
    priority = queue.PriorityQueue()
    for value in count:
        priority.put(value)
    while priority.qsize() > 1:
        one, two = priority.get(), priority.get()  # one == (1, 'a'); two == (1, 'b')
        node = Node(one, two)  # node == Node(left=(1, 'a'), right=(1, 'b'))
        priority.put((one[0]+two[0], node))  #  (2, Node(left=(1, 'a'), right=(1, 'b'))  <== error here
    return priority.get()

当您的代码将 (2, Node(left=(1, 'a'), right=(1, 'b')) 添加到 PriorityQueue 时，队列中的其他元素 (2, 'c') 具有相同的优先级，因此使用该数据元素进行排序。

因此，您需要显式忽略按数据排序(请参阅上面的文档示例以获取一些指导)，或者定义 'c' 应如何相对于 Node(left=( 1, 'a'), right=(1, 'b')) 并实现它。例如，如果您始终希望 Node 相对于某些其他数据类型排在最后:

def __lt__(self, other):
    return True

def __gt__(self, other):
    return False

反之亦然:

def __lt__(self, other):
    return False

def __gt__(self, other):
    return True

或者更复杂的东西？