基于c语言的数据结构之Huffman程序实现

background:（1）所有节点放入集合k中

（2）k中剩余节点大于两个时，取出权值最小的两个节点，构建他们为某个新节点的左右子节点，该新节点的权值为子节点权值的和，将该新节点加入k集合中

（3）若k中只剩下一个节点，则该节点即为构造出的哈夫曼树的根节点，所有非终端节点的权值和就是该Huffman树的带权路径和。

注：此处为从K中取出两个权值最小的两个节点，需要用到堆，而堆是数据结构中一种重要的结构，读者可以自行了解，它可以以o(logn)时间复杂度取出最小元素，而标准模板库中有--优先队列。利用语句：priority_queue<int> Q;但默认是大顶堆，我们需要使用小顶堆，因此用如下语句：priority_queue<int, vector<int>,greater<int>> Q;关于堆的操作如下：Q.push(x);//将元素放入堆中。Q.pop();//取出堆顶元素最小元素保存在a中。弹出堆顶元素后会自动调整为一个新的小顶堆。它的使用在之前使用过的队列一样的标准模板库queue中，所以在使用它之前我们必须做相应预处理。

#include<queue>

using namespace std;

issue:Huffman树，第一行输入一个数n，表示叶节点的个数，需要用这些叶节点生成Huffman树，根据Huffman树的概念，这些节点的所有权值，即weight，题目需要输出所有节点的值与权值的乘积之和。

输入：5

1 2 2 5 9

输出：37

source：北京邮电大学计算机研究生机试真题

code:

#include<stdio.h>
#include<queue>
using namespace std;
priority_queue<int,vector<int>,greater<int> > Q;//建立小顶堆*****此处的‘> >’之间的空格不可少否则报错
int main(){
    int n;
while(scanf("%d",&n)!=EOF){//crtl+z会退出循环
  while(Q.empty()==false){
   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;//该父节点必为非叶子节点，固累加其权值**********emphasis:所有非终端节点求和，必定是Huffman树的带权路径长
  Q.push(a+b);//求和后重新压入堆中
  }
  printf("%d\n",ans);//输出答案
}
return 0;
}