题解 | 【模板】哈夫曼编码

import sys
# 用优先级队列
# 超时，用例过7/10
# 估计最用dfs生成树，边合并边生成encoding应该能过
class Node:
    def __init__(self,weight=None,val=None) -> None:
        self.weight = weight
        self.val = val
        self.left = None
        self.right = None

from queue import PriorityQueue

n = int(input())

q = PriorityQueue()

freqs = list(map(int,input().strip().split()))

for i,freq in enumerate(freqs):
    q.put((freq, i, Node(freq,i))) # i作为第二比较因子，用于防止相同权重 优先级队列插入问题

if n == 1:
    print(freqs[0])

else:
    while not q.qsize()==1:
        freq1, _, node1 = q.get()
        freq2, _, node2 = q.get()
        head = Node()
        head.left = node1
        head.right = node2
        head.weight = freq1 + freq2
        q.put((freq1+freq2,-1,head))

    num2map = {}

    def dfs(head,coding,num2map):
        if head.left is None and head.right is None:
            num2map[head.val] = coding
            return
        if head.left:
            dfs(head.left,coding + '0', num2map)
        if head.right:
            dfs(head.right,coding+'1',num2map)
    _, _, head = q.get()
    dfs(head,'',num2map)
    res = 0
    for key, val in num2map.items():
        res += freqs[key] * len(val)
    print(res)