04080:Huffman编码树

http://cs101.openjudge.cn/practice/04080/

构造一个具有n个外部节点的扩充二叉树，每个外部节点Ki有一个Wi对应，作为该外部节点的权。使得这个扩充二叉树的叶节点带权外部路径长度总和最小：

Min( W1 * L1 + W2 * L2 + W3 * L3 + … + Wn * Ln)

Wi:每个节点的权值。

Li:根节点到第i个外部叶子节点的距离。

编程计算最小外部路径长度总和。

输入

第一行输入一个整数n，外部节点的个数。第二行输入n个整数，代表各个外部节点的权值。 2<=N<=100

输出

输出最小外部路径长度总和。

样例输入

4
1 1 3 5

样例输出

这个问题其实是一个经典的 最优二叉树 构造问题，也叫做 霍夫曼编码（Huffman Coding）。我们要构造一棵 扩充二叉树（即每个非叶子节点都有两个子节点），使得所有 叶子节点的带权路径长度和最小。

✅ 思路简述（霍夫曼算法）：

我们通过以下贪心策略构造一棵最优二叉树：

将所有权值作为初始节点，放入一个最小堆中。
重复执行以下操作直到只剩一个节点：
- 从堆中取出两个最小权值节点 a 和 b
- 合并为一个新节点，权值为 a + b
- 把这个新节点的权值加入堆
- 这次合并会产生一个代价：a + b，将其加入总路径代价中
最终累加的合并代价即为 最小外部带权路径长度总和。

✅ 示例解释

输入：

4
1 1 3 5

构造过程：

1 + 1 → 新节点权值 2，总成本 += 2
2 + 3 → 新节点权值 5，总成本 += 5
5 + 5 → 新节点权值 10，总成本 += 10
最终成本 = 2 + 5 + 10 = 17

✅ Python 实现

python

import heapq

def min_weighted_path_length(n, weights):
    heapq.heapify(weights)
    total = 0
    while len(weights) > 1:
        a = heapq.heappop(weights)
        b = heapq.heappop(weights)
        combined = a + b
        total += combined
        heapq.heappush(weights, combined)
    return total

# 读取输入
n = int(input())
weights = list(map(int, input().split()))
print(min_weighted_path_length(n, weights))

python

from heapq import heapify,heappop,heappush

class Node:
    def __init__(self,val,fre):
        self.val=val
        self.fre=fre
        self.left=None
        self.right=None
    def __lt__(self,other):
        return self.fre<other.fre
    
def HuffmanTree(val_fre):
    while len(val_fre)>1:
        left=heappop(val_fre)
        right=heappop(val_fre)
        merge=Node(None,left.fre+right.fre)
        merge.left=left
        merge.right=right
        heappush(val_fre,merge)
    return val_fre[0]

def calculate(node,depth):
    if node.left==node.right==None:
        return node.fre*depth
    return calculate(node.left,depth+1)+calculate(node.right,depth+1)

n=int(input())
val_fre=[]
fres=list(map(int,input().split()))
for i in range(n):
    val_fre.append(Node(i,fres[i]))
heapify(val_fre)
root=HuffmanTree(val_fre)
ans=calculate(root,0)
print(ans)

04080:Huffman编码树 ​

04080:Huffman编码树