将对象添加到优先级队列时得到 "not supported between instances of 'tuple' and 'list'"

Question

我正在尝试将一对元素添加到优先级队列中。当我尝试添加元素时出现此错误：

"TypeError: < not supported between instances of 'tuple' and 'list'"

我应该使用另一种方式将元素添加到 priorityQueue 而不是 .put() 吗？

我正在尝试计算霍夫曼节点

import queue
S = "testString"
map = [chr(i) for i in range(ord('a'),ord('z')+1)]
aux = auxTemp = list()
freqs = list()

def repsInS(S,map):
    reps = 0
    for i, value in enumerate(map):
        for j, value in enumerate(S):
            if(map[i]==S[j]):
                reps+=1
        aux.append(map[i])
        aux.append(reps)
        auxTemp = aux.copy()
        freqs.append(auxTemp)
        aux.clear()
        reps = 0
        freqs.sort(key= lambda x:x[1])
    return freqs

frecuencias = repsInS(S,map)

class NodoHuffman(object):
    def __init__(self, left=None, right=None, root=None):
        self.left = left
        self.right = right
        self.root = root

    def hijoTemp(self):
        return((self.left, self.right))


def HuffmanTree(frecuencias):
    objs = queue.PriorityQueue()
    for i in frecuencias:
        objs.put(i)

    while (objs.qsize() > 1):
            left = objs.get()
            right = objs.get()
            newNode = NodoHuffman(left,right)
            objs.put((left[1]+right[1],newNode))
    return objs.get()

huff = HuffmanTree(frecuencias)

Answer 1

我找到了错误背后的罪魁祸首:)。

queue.PriorityQueue class 的工作方式是存储项目列表。每当你 .put 的东西，它会使用 < 和 > 比较它来找到插入它的位置。 '.get' 只会将其从已排序的列表中弹出。

由于无法比较tuple和list，所以.put失败。这也可能是因为你之后可以更改列表，导致优先级队列中断。

一个简单的解决方法是将 repsInS 中带有 freqs.append([t, reps]) 的行更改为 freqs.append((t, reps)).

编辑：看起来还有更多...优先级队列使用对象的丰富比较魔术方法对它们进行排序。相反，我让他们使用普通列表并让节点保存自己的权重。这节省了 class 中的复杂性并使代码更易于理解。

这是经过修改和完善的代码。

import queue

test_str = 'testString'
test_list = [chr(i) for i in range(ord('a'), ord('z') + 1)]


class HuffmanNode:
    def __init__(self, weight, left=None, right=None, info=None):
        self.weight = weight
        self.left = left
        self.right = right
        self.info = info

    def hijoTemp(self):
        return self.left, self.right


def get_repeats(S, T):
    freqs = []

    for t in T:
        reps = 0
        for s in S:
            if s == t:
                reps += 1
        freqs.append((reps, t))

    freqs.sort(key=lambda x: x[0], reverse=True)
    return freqs # Return list of lists


def create_huffman_tree(freqs):
    objs = [HuffmanNode(w, info=l) for w, l in freqs]
    objs.sort(key=lambda node: node.weight, reverse=True)

    while len(objs) > 1:
        left, right = objs.pop(), objs.pop()
        weight = left.weight + right.weight
        objs.put(HuffmanNode(weight, left, right))

    return objs.pop()

if __name__ == '__main__':
    frecuencias = get_repeats(test_str, test_list)
    huffman_tree = create_huffman_tree(frecuencias)

将对象添加到优先级队列时得到 "not supported between instances of 'tuple' and 'list'"

getting "not supported between instances of 'tuple' and 'list'" when adding object to priority queue

python

class

sorting

huffman-code