题解 | #哈夫曼树#

#include<iostream>
#include<vector>
#include<queue>
using namespace std;

int main() {
	int n; // 叶节点个数
	while (cin >> n) {
		priority_queue<int, vector<int>, greater<int>> myQueue; // 创建一个小顶堆优先队列
		for (int i = 0; i < n; i++) {
			int temp;
			cin >> temp;
			myQueue.push(temp); // 将叶节点权值插入优先队列
		}
		int answer = 0; // 存储最终的答案
		while (myQueue.size() > 1) { // 当队列中还有两个及以上的节点时
			int a = myQueue.top(); // 弹出队列中权值最小的节点
			myQueue.pop();
			int b = myQueue.top(); // 弹出队列中权值次小的节点
			myQueue.pop();
			answer += (a + b); // 将两个节点的权值之和累加到答案中
			myQueue.push(a + b); // 将新的节点（权值为原两节点之和）插入队列
		}
		cout << answer << endl; // 输出最终的答案
	}

	return 0;
}