题解 | 哈夫曼编码

import sys
from collections import deque
# 给定一组字符及其出现频率（或权重），哈夫曼编码为每个字符分配一串二进制码字。
# 高频字符分配较短的编码，低频字符分配较长的编码，保证无前缀（一个码字不是另一个码字的前缀）。
# 目标是使编码后所有字符加权平均长度最短，从而压缩数据。

def huffman_length():
    n=int(sys.stdin.readline())
    freqs=list(map(int,sys.stdin.readline().split())) 
    if n<=2:
        return sum(freqs)
    freqs.sort()
    sort_q=deque(freqs)
    merge_q=deque()
    total_len=0
    def pop_min():
        if not merge_q or (sort_q and sort_q[0]<=merge_q[0]):
            return sort_q.popleft()
        return merge_q.popleft()
   
    for _ in range(n-1):
        s=pop_min()+pop_min()
        total_len+=s
        merge_q.append(s)
    return total_len

if __name__=='__main__':
    print(huffman_length())