小明在学习算法,现在他正在学习一种叫做Huffman树的数据结构。Huffman树在压缩数据、通信和加密等领域有着广泛的应用。 给出一数组pi=[p0, p1, ..., pn-1],用这个数组构造成一个Huffman树,过程如下: 1. 找到pi中最小的两个数,设为pa和pb,将pa和pb从pi中删除掉,然后将它们的和加入到pi中。这个过程的费用记为pa + pb。 2. 重复步骤1,直到pi中只剩下一个数。 在上面的操作过程中,把所有的费用相加,就得到了构造Huffman树的总费用。 请你编写一个程序,:对于给定的一个数组,输出构造Huffman树的总费用。 【输入描述】 输入两行 第一行输入整数n,表示数组的长度。 第二行n个整数,表示构成数组的元素,用空格隔开。
时间: 2024-02-05 12:13:28 浏览: 62
```python
n = int(input()) # 数组长度
nums = list(map(int, input().split())) # 数组元素
import heapq # 引入堆结构
heapq.heapify(nums) # 将nums转换成堆结构
cost = 0 # 记录总费用
while len(nums) > 1:
a = heapq.heappop(nums) # 弹出最小的两个数
b = heapq.heappop(nums)
s = a + b # 计算和
cost += s # 更新总费用
heapq.heappush(nums, s) # 将和加入堆中
print(cost) # 输出结果
```
输入样例:
```
5
1 2 3 4 5
```
输出样例:
```
33
```
阅读全文