哈夫曼树---POJ3253

http://poj.org/problem?id=3253

这就是 最典型的哈夫曼树的题型，我们就根据这道题学习一下哈夫曼树

这是最开始我们把21据下来之后我们据下8，然后再据下5得到34，可以看出13被用到2次，8被用到1次13*2+8=34。

这幅图片，我们先据下21，再据下5，再据下8得到34，即16*2+5=37。

所以，对于这道题，我们运用贪心的思想和哈夫曼树

 #include<queue>

 #include<stdio.h>

 using namespace std;

 int main()

 {

     long long int sum;

     int i,n,t,a,b;

     while(~scanf("%d",&n))

     {

         priority_queue<int,vector<int>,greater<int> >q;

         for(i=; i<n; i++)

         {

             scanf("%d",&t);

             q.push(t);

         }

         sum=;

         if(q.size()==)

         {

             a=q.top();

             sum+=a;

             q.pop();

         }

         while(q.size()>)

         {

             a=q.top();

             q.pop();

             b=q.top();

             q.pop();

             t=a+b;

             sum+=t;

             q.push(t);

         }

         printf("%lld\n",sum);

     }

     return ;

 }