题解 | #【模板】哈夫曼编码#

#include <stdio.h>
//除了小顶堆，不需要任何其他数据结构
//插入
void HeapInsert(long long* Heap, long long val, int size) {
    Heap[size] = val;
    while (Heap[size] < Heap[(size - 1) / 2]) {
     long long tmp = Heap[size];
        Heap[size] = Heap[(size - 1) / 2];
        Heap[(size - 1) / 2] = tmp;
        size = (size-1)/2;
    }
}
//取出
void HeapPop(long long* Heap, int size) {

    Heap[0] = Heap[size];
    int start = 0;
    int left = 2 * start + 1;
    while (left < size) {
        if (left + 1 < size && Heap[left] > Heap[left + 1]) {
            left = left + 1;
        }
        if (Heap[start] > Heap[left]) {
            long long temp = Heap[start];
            Heap[start] = Heap[left];
            Heap[left] = temp;
            start = left;
            left = 2*start+1;
        }else{
            break;
        }
    }

}
int main() {
    int quality;
    scanf("%d", &quality);
    long long Heap[200001];
    int size = 0;
    for (int i = 0; i < quality; i++) {
        long long tmp ;
        scanf("%lld", &tmp);
        HeapInsert(Heap, tmp, size);
        size++;
    }

//   for(int i = 0;i<quality;i++){
//     printf("%lld ",Heap[i]);
//  }
long long result = 0;
    while (size >= 2) {
        long long val1 = Heap[0];
        HeapPop(Heap, size - 1);
        size--;
        long long val2 = Heap[0];
        HeapPop(Heap, size - 1);
        size--;
        result = val1+val2+result; //原因见图
        long long val3 = val1+val2;
        HeapInsert(Heap, val3, size);
        size++;
	
    }
    printf("%lld",result);
    return 0;
}