数据结构：解读哈夫曼树

哈夫曼树简介

在一棵数中，从任意一个结点到达另一个结点的通路被称为路径，改路径上所需经过的边的个数被称为该路径的长度。

给定n个结点和它们的权值，以它们为叶子结点构造一颗带权路径长度和最小的二叉树，该二叉树即为哈夫曼树，同时也被称为最优数。

哈夫曼树的求法

将所有结点放入集合K。

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

若集合K中仅剩余一个结点，该结点即为构造出的哈夫曼树的根节点，所有构造得到的中间结点的权值和即为该哈夫曼树的带权路劲和。

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

priority_queue<int> Q

这样建立的堆其默认为大顶锥，而在哈夫曼树中，我们恰恰需要取得堆中最小的元素，预算我们使用如下语句定义一个小顶堆。

priority_queue<int, vector<int>,greater<int>> Q

代码块

priority_queue

,greater

> Q; //建立一个小顶堆int main(){ int n; while(scanf("%d",&n)!=EOF){ while(Q.empty()==false) Q.pop(); //清空堆中的元素 for(int i=1;i<=n;i++){ //输入n个叶子结点权值 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;}

转载地址：http://ttgpa.baihongyu.com/

你可能感兴趣的文章