1289 Huffman Code

説明
実践は真理を検証する唯一の基準である.
多くの授業は自分の手で実践してこそ本当に身につけることができる.次の教科書のハフマンコードについて見てみましょう.
今、文章があります.バイナリ接頭辞符号化で文章に現れたすべての文字を符号化して、符号化後の文章の総長を最短にしてください.
これはまさに教科書でハフマンコードが解決した問題だ.やってみよう!
入力
複数組入力、1番目の正の整数Tはグループ数を表す.
各組の第1行には正の整数nがあり、1≦n≦100000は使用される文字種数を表す.
次の動作nの正の整数は、各文字が文章に現れる回数を表す.
しゅつりょく
出力符号化の最小長さ
サンプル入力
131 2 3
サンプル出力
9
 
 
 
この問題はスタックソートを使用します

#include <iostream>
#include <ctime>
using namespace std;

int a[100002];

void swap(int& a, int& b)
{
	int temp = a;
	a = b;
	b = temp;
}

void heapAdjust(int h[], int s, int m)
{
	int rc = h[s];
	int j;
	for(j = 2 *s; j <= m; j *= 2)
	{
		if(j < m && h[j + 1] < h[j])
		{
			j ++;
		}
		if(rc <= h[j])
		{
			break;
		}
		h[s] = h[j];
		s = j;
	}
	h[s] = rc;
}

int calc_huff(int h[], int n)
{
	int i;
	for(i = n / 2; i > 0; i --)
	{
		heapAdjust(h, i, n);
	}
	i = n;
	int sum = 0;
	while(i > 1)
	{
		swap(h[1], h[i]);
		heapAdjust(h, 1, i - 1);
		i --;
		swap(h[1], h[i]);
		heapAdjust(h, 1, i - 1);
		sum = sum + h[i] + h[i + 1];
		h[i] = h[i] + h[i + 1];
	}
	return sum;
}

int main()
{
	int t;
	cin >> t;
	while(t --)
	{
		int n;
		cin >> n;
		int i;
		for(i = 1; i <= n; i ++)
		{
			cin >> a[i];
		}
		cout << calc_huff(a, n) << '
';
	}
	return 0;
}