Python，了解Huffman代码2

Question

我一直在尝试理解Rosetta code用Python编写的霍夫曼代码

我理解了它的大部分，并对其中的一些部分进行了评论：

from heapq import heappush, heappop, heapify 
from collections import defaultdict
import collections

txt = "abbaac!ccc" #txt is variable for string which will be encoded
symb2freq = collections.Counter(txt) #counts letter frequency
                                     #and puts in dictionary

def encode(symb2freq): #define a function

    heap = [[freq, [symbol, ""]] for symbol, freq in symb2freq.items()] #converts dictionary to a list in order to sort out alphabets in terms of frequencies

    heapify(heap) #This sorts out the list so that 1st element is always the
                  #smallest

    while len(heap) > 1:#while there is more than 1 element in the list

        left = heappop(heap) #Takes the lowest frequency from the list

        print("lo=", left)

        right = heappop(heap) #Takes the lowest frequency from the list        

        for x in left[1:]: 
            x[1] = '0' + x[1]
        for x in right[1:]:
            x[1] = '1' + x[1]
        add_freq= [left[0] + right[0]] + left[1:] + right[1:] #adds the frequencies and inserts frequency, symbol and alphabet (0 or 1) into one list e.g. [3, ['!', '0'], ['b', '1']]

        heappush(heap, add_freq )#inserts add_freq into heap

    return sorted(heappop(heap)[1:], key=lambda p: (len(p[-1]), p)) #What is this doing?

huff = encode(symb2freq)
print ("Symbol\tWeight\tHuffman Code")
for p in huff:
    print ("%s\t%s\t%s" % (p[0], symb2freq[p[0]], p[1]))

有一句话我不明白：

return sorted(heappop(heap)[1:], key=lambda p: (len(p[-1]), p)) #What is this doing?

为了更好地理解，我对它做了一些更改。

Answer 1

在while循环之后，堆只剩下一个元素。

heappop(heap)应该会得到最后一个元素。

heappop( heap )1:获取最后一个heap元素的整个列表并删除第一个元素，我不知道为什么。

然后这个列表是按排序的(...，key=lambda p：(len(p-1)，p))排序的。这意味着这个列表中的顺序是根据key中定义的函数重新排列的。此函数根据元素的长度或元素本身对列表进行排序。这应该从最短到最长的顺序排列你的霍夫曼编码。

所以这行代码基本上是对生成的代码进行排序。