基礎哈夫曼樹-最簡單的

writer：pprp

哈夫曼樹是最優二叉樹，帶權值的二叉樹

題意大概：

給n個數，經過計算得到最優二叉樹的最小權值；

代碼如下：（單個測試用例）

#include <iostream>
#include <queue>
#include <vector>
//最優二叉樹：帶權值的二叉樹
using namespace std;

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

//一組資料
int main()
{
    int n;
    int tmp;
    int x,y;
    cin >> n;
    for(int i = 0 ; i < n ; i++)
    {
        cin >> tmp;
        x = tmp;
        p.push(x);

    }
    int sum = 0;

    cout << p.top() << endl;
    while(!p.empty())
    {
      
        x = p.top(); //取出一個最小值
        p.pop();
        if(n == 1)
            break;
        y = p.top();  //取出一個最小值
        p.pop();
        n--;
        x += y;
        sum += x;
        
        p.push(x);
    }

    cout << sum << endl;
    return 0;
}      

代碼改變世界