定義

哈夫曼樹又稱最優(yōu)二叉樹，是一種帶權(quán)路徑長度最短的二叉樹。

所謂樹的帶權(quán)路徑長度，就是樹中所有的葉結(jié)點(diǎn)的權(quán)值乘上其到根結(jié)點(diǎn)的路徑長度（若根結(jié)點(diǎn)為0層，葉結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑長度為葉結(jié)點(diǎn)的層數(shù)）。

樹的路徑長度是從樹根到每一結(jié)點(diǎn)的路徑長度之和，記為WPL=（W1*L1+W2*L2+W3*L3+...+Wn*Ln），N個(gè)權(quán)值Wi（i=1,2,...n）構(gòu)成一棵有N個(gè)葉結(jié)點(diǎn)的二叉樹，相應(yīng)的葉結(jié)點(diǎn)的路徑長度為Li（i=1,2,...n）。

可以證明哈夫曼樹的WPL是最小的。

給定N個(gè)權(quán)值作為N個(gè)葉子結(jié)點(diǎn)，構(gòu)造一棵二叉樹，若該樹的帶權(quán)路徑長度達(dá)到最小，稱這樣的二叉樹為最優(yōu)二叉樹，也稱為哈夫曼樹(Huffman Tree)。

哈夫曼樹是帶權(quán)路徑長度最短的樹，權(quán)值較大的結(jié)點(diǎn)離根較近。

實(shí)例引入

現(xiàn)在有這樣一個(gè)經(jīng)典問題：果子合并。

現(xiàn)在得到很多果子，需要把這些果子合并成一堆。每一次合并，可以把兩堆果子合并到一起，消耗的體力等于兩堆果子的重量之和?？梢钥闯?，所有的果子經(jīng)過 n−1 次合并之后，就只剩下一堆了。在合并果子時(shí)總共消耗的體力等于每次合并所耗體力之和。

假定每個(gè)果子重量都為 1，并且已知果子的種類數(shù)和每種果子的數(shù)目，你的任務(wù)是設(shè)計(jì)出合并的次序方案，使耗費(fèi)的體力最少，并輸出這個(gè)最小的體力耗費(fèi)值。

例如有 3 種果子，數(shù)目依次為 1，2，9?？梢韵葘?nbsp;1、2 堆合并，新堆數(shù)目為 3，耗費(fèi)體力為 3。

接著，將新堆與原先的第三堆合并，又得到新的堆，數(shù)目為 12，耗費(fèi)體力為 12。所以總共耗費(fèi)體力=3+12=15?？梢宰C明 15 為最小的體力耗費(fèi)值。

我們把這幾個(gè)果子看成樹的葉子

 然后通過逐次合并其中兩個(gè)葉子（果子），使根節(jié)點(diǎn)的權(quán)值最小，根據(jù)上面的分析先合并1，2得到3，之后合并3，9得到12。

其中我們要計(jì)算的便是產(chǎn)生的新節(jié)點(diǎn)的權(quán)值，把這先權(quán)值相加，即是最后要求的體力值。

進(jìn)一步分析可以發(fā)現(xiàn)，假設(shè)初始狀態(tài)下我們有四個(gè)點(diǎn)，是四個(gè)點(diǎn)之間的最優(yōu)解問題，當(dāng)我們合并其中兩個(gè)點(diǎn)之后就變成了三個(gè)點(diǎn)的最優(yōu)解問題，以此類推；

而且如果保證每次選的兩個(gè)數(shù)都是最小的（最優(yōu)的），那么接下來都是最優(yōu)解的情況了。

由于數(shù)據(jù)輸入是并不是按照從小到大排列，故可以使用小根堆來做。 

 代碼

#include <bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	scanf("%d", &n);
	priority_queue<int, vector<int>, greater<int>> heap;
	while (n--)
	{
		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;
}

到此這篇關(guān)于C++最優(yōu)二叉樹哈夫曼樹算法解析的文章就介紹到這了,更多相關(guān)C++哈夫曼樹內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論