题解|哈夫曼树

题目链接

要求输出哈夫曼树的带权路径长度，优先队列默认是大根堆排序，若元素取反存入就是小根堆存储，每次取出最小的两个数相加，结果再存入优先队列比较，直到队列中仅剩一个元素，即为wpl的相反数。

#include<stdio.h>
#include<string>
#include<queue>
using namespace std;

int main() {
	int N,data;
	priority_queue<int> myqueue;
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf("%d", &data);
		myqueue.push(-1 * data);//小根堆
	}
	int a = 0, b = 0, wpl = 0;
	while (myqueue.size()>1){
		//出队2个
		a = myqueue.top();
		myqueue.pop();
		b = myqueue.top();
		myqueue.pop();
		wpl += a + b;
		//入队1个
		myqueue.push(a + b);
	}
	printf("%d\n", -1 * wpl);
	return 0;

}