九度OJ 题目1172：哈夫曼树

题目描述：

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

输入：

输入有多组数据。
每组第一行输入一个数n，接着输入n个叶节点（叶节点权值不超过100，2<=n<=1000）。

输出：

输出权值。

样例输入：

5
1 2 2 5 9

样例输出：

37

=================================
吐槽:VC6里面智能提示好像到while语句之类的循环里面就会失效，然后就只能盲打..Orz…
=================================

#include
#include
#include
using namespace std;
struct Node
{
int val;
Node *parent;
Node()
{
parent = NULL;
}
int getHeight()
{
int h = 0;
Node *p = parent;
while(p != NULL)
{
h++;
p = p->parent;
}
return h;
}
};
bool compare(Node *x, Node *y)
{
return x->val > y->val;
}
int main()
{
int N;
while(cin >> N)
{
vector workingSet;
Node *nodes = new Node[N]; //Primitive Nodes
int i;
for(i=0; i> nodes[i].val;
workingSet.push_back(&nodes[i]);
}
///
while(workingSet.size() > 1)
{
sort(workingSet.begin(), workingSet.end(), compare);
Node *small1 = workingSet.back();
workingSet.pop_back();
Node *small2 = workingSet.back();
workingSet.pop_back();
//Combine
Node *combined = new Node;
combined->val = small1->val + small2->val;
small1->parent = combined;
small2->parent = combined;
workingSet.push_back(combined);
}
//output
int sum = 0;
for(i=0; i