第六讲 贪心

哈夫曼树

由于哈夫曼树的根节点是由两个子节点合并而来，所以哈夫曼树一定是完全二叉树

做法是每一次挑出最小的两堆

1. 在所有数里面，数最小的两个数一定是深度最深的两个点且可以互为兄弟节点

每一次求最小值，可以用小根堆、优先队列，小根堆就是每次的top()是最小值

 std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;

vector<int>指的是用来存储元素的底层容器

大根堆就是每次的top()都是最大值

std::priority_queue<int> maxHeap;

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

int n;
int main () {
    cin >> n;
    priority_queue<int, vector<int>, greater<int>> heap;

    for (int i = 0; i < n; i++) {
        int x;
        scanf("%d", &x);
        heap.push(x);
    }
    int res = 0;
    while (heap.size() > 1) {
        int a = heap.top();
        heap.pop();
        int b = heap.top();
        heap.pop();
        res += a + b;
        heap.push(a + b);
    }
    printf("%d\n", res);
    return 0;
}