巢穴

about:blank

P3253

哈夫曼树
用二叉堆维护logn的最小优先队列

#include <iostream>

using namespace std;

const int MAXN=20001;
int n;
long long num[MAXN];
int len=0;

void insert(long long x)
{
 len++;
 num[len]=x;
 int pos=len;
 while(pos>1)
 {
  if (num[pos]<num[pos/2])
  {
   swap(num[pos],num[pos/2]);
   pos/=2;
  }
  else break;
 }
}
long long remove()
{
 long long x=num[1];
 swap(num[1],num[len]);
 len--;
 int pos=1;
 int k;
 while(pos*2<=len)
 {
  int l=pos*2,r=pos*2+1;
  if (r>len||num[l]<num[r])
  {
   k=l;
  }
  else k=r;
  if (num[pos]>num[k]) {swap(num[pos],num[k]);pos=k;} else break;
 }
 return x;
}
int main()
{
    cin>>n;
    long long x;
    for (int i=1;i<=n;i++)
    {
     cin>>x;
     insert(x);
    }    
    long long result=0;
    while(len>1)
    {
     long long x=remove();
     long long y=remove();
     long long z=x+y;
     result+=z;
     insert(z);
    }
    cout<<result<<endl;
    system("pause");
    return 0;
}

posted on 2009-10-24 12:30 Vincent 阅读(82) 评论(0)  编辑 收藏 引用 所属分类: 数据结构与算法


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理