题解 | 哈夫曼树 优先队列(大根堆)

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <queue>  // 小根堆 头文件
using namespace std;

int main(){
	// 默认大根堆
	priority_queue<int> pqueue;  // 存储权值的相反数(使用再相反数)得到小根堆
	int n;
	scanf("%d", &n);
	for(int i=0;i<n;i++){
		int leaf;
		scanf("%d",&leaf);
		// pqueue.push(-leaf);
		pqueue.push(-1*leaf);  // 存储权值相反数
	}

	int wpl = 0;
	// 2个结点以上才合并结点求wpl
	while (pqueue.size() >= 2) {
		int leaf1 = pqueue.top();
		pqueue.pop();
		int leaf2 = pqueue.top();
		pqueue.pop();
		wpl += leaf1 + leaf2;  // 最后统一取相反
		pqueue.push(leaf1 + leaf2);  // 合并结点重新压回队列
	} 

	printf("%d\n",-1*wpl);  // 取反即为wpl

	return 0;
}