TypeError例外：「<」「タプル」のインスタンスと「STR」

Question

間でサポートされていない私は次の通りであるハフマンツリーを構築する方法があります

def buildTree(tuples) : 
    while len(tuples) > 1 : 
     leastTwo = tuple(tuples[0:2])     # get the 2 to combine 
     theRest = tuples[2:]       # all the others 
     combFreq = leastTwo[0][0] + leastTwo[1][0]  #enter code here the branch points freq 
     tuples = theRest + [(combFreq,leastTwo)]  # add branch point to the end 
     tuples.sort()         # sort it into place 
    return tuples[0]   # Return the single tree inside the list 

を私は次のパラメータと機能を供給しつつ。

[(1, 'b'), (1, 'd'), (1, 'g'), (2, 'c'), (2, 'f'), (3, 'a'), (5, 'e')] 

デバッグ、私はエラーがにあった見つけている間、私は

File "<stdin>", line 7, in buildTree 
    tuples.sort() 
TypeError: '<' not supported between instances of 'tuple' and 'str' 

としてエラーが出ます3210。

Answer 1

(priority, (node, node))フォームで内部ノードを作成するため、エラーがスローされます。もしあれば、ハフマンツリーを構築するため

>>> inner = (combFreq, leastTwo) 
>>> inner 
(2, ((1, 'b'), (1, 'd'))) 
>>> theRest[1] 
(2, 'c') 
>>> theRest[1] < inner 
Traceback (most recent call last): 
    File "<stdin>", line 1, in <module> 
TypeError: '<' not supported between instances of 'str' and 'tuple' 

：等しい優先順位のために、Pythonは次いで、内側のノードから(node, node)タプルとリーフノードからのシンボル（SO (priority, symbol)ノードタプルの2番目の要素）を比較しようとしますノードのあなたの配列をソートしたい、あなただけの本当にタプル（シンボルまたは子ノード）の残りの部分を無視して、優先順位にソートする必要があります。

tuples.sort(key=lambda t: t[0]) 

その補正では、あなたのbuildTree()関数がツリーを生成します。

>>> buildTree([(1, 'b'), (1, 'd'), (1, 'g'), (2, 'c'), (2, 'f'), (3, 'a'), (5, 'e')]) 
(15, ((6, ((3, 'a'), (3, ((1, 'g'), (2, 'c'))))), (9, ((4, ((2, 'f'), (2, ((1, 'b'), (1, 'd'))))), (5, 'e'))))) 

個人的には、優先度キューを代わりに使用して、毎回ソーティングを避けます。 How to implement Priority Queues in Python?