Huffuman树-题解（C++代码） 优先队列priority_queue实现以及vector实现

解题思路:
按照题目要求以及Huffuman树的编码形式来解题，解题的关键在于取出最小的两个数相加，再把相加的结果累加到答案中并把它加入容器中重新排序就行了。可以用vector和优先队列priority_queue来实现，当然也可以用数组来实现，用优先队列更容易理解。vector就不用说了，关于优先队列priority_queue简单说明一下。 priority_queue包含在头文件#include <queue>, 他和queue不同的就在于我们可以自定义其中数据的优先级, 让优先级高的排在队列前面,优先出队。

优先队列具有队列的所有特性，包括基本操作，只是在这基础上添加了内部的一个排序，它本质是一个堆实现的

定义：priority_queue<Type, Container, Functional>
Type 就是数据类型，Container 就是容器类型（Container必须是用数组实现的容器，比如vector,deque等等，但不能用 list。STL里面默认用的是vector），Functional 就是比较的方式，当需要用自定义的数据类型时才需要传入这三个参数，使用基本数据类型时，只需要传入数据类型，默认是大顶堆
一般是：

//升序队列

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

//降序队列

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

//greater和less是std实现的两个仿函数（就是使一个类的使用看上去像一个函数。其实现就是类中实现一个operator()，这个类就有了类似函数的行为，就是一个仿函数类了）

这就实现了对queue的排序，然后就可以用queue的思路来解决此题。

注意事项:

参考代码:

//vector解法
#include<bits/stdc++.h>
using namespace std;
vector<int>vt;
int main() {
    int n;
    cin>>n;
    int x1;
    for(int i = 1; i<=n;i++) {
        scanf("%d",&x1);
        vt.push_back(x1);
    }
    int sum=0;
    while(!vt.empty()) {
        sort(vt.begin(),vt.end());
        int x,y;
        x = vt.front();   //x=*vt.begin();
        vt.erase(vt.begin());
        if(vt.empty())
            break;
        y= vt.front();
        vt.erase(vt.begin());
        int add;
        add = x + y;
        sum+=add;
    //  cout<<"sum="<<sum<<endl;
        vt.push_back(add);
    }
    cout<<sum<<endl;
    return 0;
}

//priority_queue解法
#include<bits/stdc++.h>
using namespace std;
priority_queue<int,vector<int>,greater<int> >que;
int main() {
    int n;
    cin>>n;
    int x1;
    for(int i = 1; i<=n;i++) {
        scanf("%d",&x1);
        que.push(x1);
    }
    int sum=0;
    while(!que.empty()) {
        int x,y;
        x = que.top(); 
        que.pop();
        if(que.empty())
            break;
        y= que.top();
        que.pop();
        int add;
        add = x + y;
        sum+=add;
    //  cout<<"sum="<<sum<<endl;
        que.push(add);
    }
    cout<<sum<<endl;
    return 0;
}