造树+返回WPL

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;
typedef long long ll;

const int N = 1010;
int a[N];
/*
给定 N 个权值作为 N 个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，
称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。
*/


struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

TreeNode* minHeap[N];
int sz = 0;

void pre_print(TreeNode* rt){
    if(rt == nullptr) return;
    printf("%d ", rt->val);
    pre_print(rt->left);
    pre_print(rt->right);
}

void up(int i){
    int parent = i >> 1;
    while(parent >= 1){
        if(minHeap[parent]->val > minHeap[i]->val){
            swap(minHeap[parent], minHeap[i]);
            i = parent;
            parent = i >> 1;
        }
        else break;
    }
}

void down(int i){
    int left = i << 1;
    while(left <= sz){
        if(left + 1 <= sz && minHeap[left + 1]->val < minHeap[left]->val) left++;
        if(minHeap[left]->val < minHeap[i]->val){
            swap(minHeap[left], minHeap[i]);
            i = left;
            left = i << 1;
        }
        else break;
    }
}

void insert(int x){
    minHeap[++sz] = new TreeNode(x);
    up(sz);
}

void extract(){
    swap(minHeap[1], minHeap[sz]);
    sz--;
    down(1);
}

TreeNode* top(){
    return minHeap[1];
}

void makeMinHeap(int a[], int n){
    sz = n;
    for(int i = 1; i <= n; i++) minHeap[i] = new TreeNode(a[i]);
    for (int i = sz >> 1; i >= 1; i--) {
        down(i);
    }
}

ll construct(TreeNode*& rt){
    // 建立huffman tree，返回WPL
    ll ans = 0;
    TreeNode* node;
    while(sz > 1){
        auto w1 = top();
        extract();
        auto w2 = top();
        node = new TreeNode(w1->val + w2->val);
        node->left = w1, node->right = w2;
        minHeap[1] = node;
        down(1);
        ans += w1->val + w2->val;
    }
    rt = node;
    return ans;
}

int main(){
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    makeMinHeap(a, n);
    TreeNode* rt;
    ll ans = construct(rt);
    cout << ans << endl;
}