Fork me on GitHub

数据结构与算法-树的应用(一)-哈夫曼树


数据结构与算法-树的应用(一)-哈弗曼树

​ 在一棵树中,从任意一个结点到达另一个结点的通路被称为路径,该路径上所需要经过的边的个数被称为该路径的长度。从根节点到达该结点的路径长度再乘以该结点权值被称为该结点的带权路径长度。树中所有叶子节点的带权路径长度之和为该树的带权路径长度和。给定n个结点和它们的权值,以它们为叶子结点构造一棵带权路径长度和最小的二叉树,该二叉树即为哈夫曼树,同时也被称为最优树。

​ 给定结点的哈弗曼树可能不唯一,所以关于哈弗曼树的机试题往往需要求解的是其最小带权路径长度和。回顾一下我们所熟知的哈弗曼树求法。

​ (1) 将所有结点放入集合K。

​ (2) 若集合K中剩余结点大于2个,则取出其中权值最小的两个结点,构造它们同时为某个新结点的左右子结点,该新结点是他们共同的双亲结点,设定它的权值为其两个孩子结点的权值和。并将该父亲结点放入集合K。重复步骤(2)或(3)。

​ (3) 若集合K中仅剩一个结点,该结点即为构造出的哈弗曼树的根结点,所有构造得到的中间结点(即哈弗曼树上非叶子节点)的权值和即为该哈弗曼树的带权路径和。

​ 为了方便快捷高效率的求得集合K中权值最小的两个元素,我们需要使用堆数据结构。它可以以O(logn)的复杂度取得n个元素中的最小元素。为了绕过对堆的实现,我们使用标准模板库中的相应的标准模板-优先队列。

​ 利用语句 priority_queue<int> Q;

​ 建立一个保存元素为int的堆Q,但是请特别注意这样建立的堆其默认为大顶堆,即我们从堆顶取的的元素为整个堆中最大的元素。而在求哈弗曼树中,我们恰恰需要取得堆中最小的元素,于是我们使用如下语句定义一个小顶堆:

1
2
> priority_queue<int,vector<int>>,greater<int>> Q;
>

关于堆的有关操作如下:

1
2
> Q.push(x);
>

将元素x放入堆Q中

1
2
> int a = Q.top();
>

取出堆顶元素,即最小的元素保存在a中。

1
2
> Q.pop();
>

弹出堆顶元素,取出后堆会自动调整为一个新的小顶堆。

题目描述

​ 哈弗曼树,第一行输入一个数n,表示叶结点的个数。需要用这些叶结点生成哈弗曼树,根据哈弗曼树的概念,这些结点有权值,即weight,题目需要输出所有结点的值与权值的乘积之和。

输入:

​ 输入有多组数据。每组第一行输入一个数n,接着输入n个叶结点(叶结点权值不超过100,2<=n<=1000)。

输出:

​ 输出权值

样例输入:

1
2
5
1 2 2 5 9

样例输出:

1
37

源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
#include <cstdio>
#include <queue>

using namespace std;

priority_queue<int,vector<int>,greater<int> > Q; // 建立一个小顶堆

int main(void){
int n;
while(scanf("%d",&n)!=EOF){
while(!Q.empty()) Q.pop(); // 清空小顶堆
for(int i = 1 ; i <= n ; i++){
int x;
scanf("%d",&x);
Q.push(x);
}
int ans = 0; // 保存答案

while(Q.size() > 1){
int a = Q.top();
Q.pop();
int b = Q.top();
Q.pop(); // 取出堆中两个最小元素,它们为同一个结点的左右孩子,且该双亲结点的权值为它们的和
ans += a+b; // 该双亲结点必为非叶子结点,固累加其权值
Q.push(a+b);
}
printf("%d\n",ans);
}

return 0;
}

运行结果:

坚持原创技术分享,您的支持将鼓励我继续创作
-------------本文结束感谢您的阅读-------------
0%