# 12100: 【原2100】哈夫曼树

### 题目描述

author: tomtao 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/2100

## Sample Input

3
1
2
3


## Sample Output

9


## Sample Explanation

哈夫曼编码：
1：00   len[1] = 2
2：01   len[2] = 2
3：1    len[3] = 1
Output = len[1] * F[1]+len[2]*F[2] + len[3]*F[3] = 2 * 1 + 2 * 2 + 1 * 3）


## Limits

Time limit: 1000ms, memory limit: 50000kb.

## q4x3's solution

/**
* 最小堆 + 哈夫曼
* 每次把最小的两个取出来加到一起
* 加入ans
* 并放回堆中
**/
#include <iostream>
#include <stdio.h>

using namespace std;

long long int N, F[50233], ans;

void down(long long int rt, long long int size) {
long long int tmp = F[rt];
if((rt << 1) > size) return;
else if((rt << 1 | 1) > size) {
if(tmp > F[rt << 1]) {
F[rt] = F[rt << 1];
F[rt << 1] = tmp;
}
return;
} else {
long long int chi1 = F[rt << 1], chi2 = F[rt << 1 | 1];
if(chi1 < tmp && chi1 <= chi2) {
F[rt] = chi1;
F[rt << 1] = tmp;
down(rt << 1, size);
} else if(chi2 < tmp && chi2 <= chi1) {
F[rt] = chi2;
F[rt << 1 | 1] = tmp;
down(rt << 1 | 1, size);
}
}
}

void build() {
for(long long int i = N / 2;i > 0;-- i) {
down(i, N);
}
}

void op(long long int size) {
long long int head = F[1];
F[1] = F[size];
down(1, size - 1);
F[1] += head; ans += F[1];
down(1, size - 1);
}

int main() {
scanf("%lld", &N);
for(long long int i = 1;i <= N;++ i)
scanf("%lld", &F[i]);
build();
for(long long int i = 0;i < N - 1;++ i) {
op(N - i);
}
cout << ans << endl;
return 0;
}


## victrid's solution

#include <cstdio>
#include <iostream>
using namespace std;
int N;
struct node {
int value;
int index;
bool isleaf;
node* left;
node* right;
node& operator=(const node& rhs) {
if (this == &rhs)
return *this;
value = rhs.value;
index = rhs.index;
left  = rhs.left;
right = rhs.right;
return *this;
}
};
void swap(node& n1, node& n2) {
node tmp = n1;
n1       = n2;
n2       = tmp;
return;
}
node* strage[200000];
void siftup(int nodec) {
if (nodec == 1 || nodec == 0)
return;
if (strage[nodec]->value < strage[nodec >> 1]->value) {
swap(strage[nodec], strage[nodec >> 1]);
siftup(nodec >> 1);
}
return;
}
void heapify(int nodec, int treesize) {
if (nodec >= treesize)
return;
if (nodec << 1 <= treesize && strage[nodec]->value > strage[nodec << 1]->value) {
swap(strage[nodec], strage[nodec << 1]);
heapify(nodec << 1, treesize);
}
if ((nodec << 1 | 1) <= treesize && strage[nodec]->value > strage[nodec << 1 | 1]->value) {
swap(strage[nodec], strage[nodec << 1 | 1]);
heapify(nodec << 1 | 1, treesize);
}
return;
}
node* construct() {
scanf("%d", &N);
if (N == 0)
return nullptr;
for (int i = 1; i <= N; i++) {
strage[i] = new node;
scanf("%d", &(strage[i]->value));
strage[i]->index  = i;
strage[i]->left   = nullptr;
strage[i]->right  = nullptr;
strage[i]->isleaf = true;
}
for (int i = 2; i <= N; i++) {
siftup(i);
}
int treestrt = N;
while (treestrt != 1) {
node* ptrf = strage[1];
strage[1]  = strage[treestrt];
treestrt--;
heapify(1, treestrt);
node* vs   = new node;
vs->value  = ptrf->value + strage[1]->value;
vs->left   = ptrf;
vs->right  = strage[1];
vs->isleaf = false;
strage[1]  = vs;
heapify(1, treestrt);
}
return strage[1];
}
long long answ = 0;
void traverse(node* root, int level) {
if (root->isleaf) {
answ += level * root->value;
return;
}
if (root->left != nullptr)
traverse(root->left, level + 1);
if (root->right != nullptr)
traverse(root->right, level + 1);
}
int main() {
node* ans = construct();
if (ans != nullptr)
traverse(ans, 0);
printf("%lld", answ);
return 0;
}


## yyong119's solution

#include <algorithm>
#include <cstdio>
const int MAXN = 50010;
int a[MAXN];

void HeapAdjust(int i , int size) {

for (;i <= (size >> 1);) {
int L = i << 1, R = i << 1 | 1, maxIndex = i;
if (a[maxIndex] > a[L] && L <= size) maxIndex = L;
if (a[maxIndex] > a[R] && R <= size) maxIndex = R;
if (maxIndex != i) std::swap(a[i], a[maxIndex]);
else break;
i = maxIndex;
}
}

int main() {

int size; scanf("%d", &size);
for (int i = 1; i <= size; ++i) scanf("%d", &a[i]);

for (int i = (size >> 1); i > 0; --i) HeapAdjust(i, size);

int tmp = size, temp = 0; long long ans = 0;
for (int i = 1; i < size; ++i) {

temp = a[1];
a[1] = a[tmp--];