Problem Description

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

int main()
{
    int n,temp,ans;
    Node a,b;
    while (cin>>n)
    {
        ans=0;
        vector<Node> heap;
        for (int i=0;i<n;i++) {
            cin>>temp;
            Node node;
            node.deep=0;
            node.weight=temp;
            heap.push_back(node);
        }
        make_heap(heap.begin(),heap.end(),greater<int>());//默认Less，最大堆
        while (heap.size()>1)
        {
//            for (vector<Node>::iterator i=heap.begin();i!=heap.end();i++)
//            {
//                cout<<*i<<" ";
//            }
            cout<<"\n";
            pop_heap(heap.begin(),heap.end(),greater<int>());//这些都需要加参数
            a=heap.back();
            heap.pop_back();
            pop_heap(heap.begin(),heap.end(),greater<int>());
            b=heap.back();
            heap.pop_back();
            Node c;
            c.deep
            c.weight=a.weight+b.weight;
            heap.push_back(a+b);
            ans+=a+b;
            push_heap(heap.begin(),heap.end(),greater<int>());
        }

        cout<<ans<<"\n";
    }
    return 0;
}
   

注意事项

1.WPL有一个简便运算，就是所有非叶子节点的权重和，知道这一点就容易多了
2.priority_queue内部也是使用vector容器，使用make_heap\push_heap两个函数的最大堆，这两个函数默认都是less，故要用的话每次都要改参数