基于C#實(shí)現(xiàn)哈夫曼樹(shù)算法
更新時(shí)間：2023年11月30日 15:51:48 作者：神仙別鬧
哈夫曼樹(shù)又稱最優(yōu)二叉樹(shù),也就是帶權(quán)路徑最短的樹(shù),對(duì)于哈夫曼樹(shù),我想大家對(duì)它是非常的熟悉,使用下面我們就來(lái)學(xué)習(xí)一下如何通過(guò)C#實(shí)現(xiàn)哈夫曼樹(shù)算法吧
赫夫曼樹(shù)又稱最優(yōu)二叉樹(shù)，也就是帶權(quán)路徑最短的樹(shù)，對(duì)于赫夫曼樹(shù)，我想大家對(duì)它是非常的熟悉，也知道它的應(yīng)用場(chǎng)景，但是有沒(méi)有自己親手寫(xiě)過(guò)，這個(gè)我就不清楚了，不管以前寫(xiě)沒(méi)寫(xiě)，這一篇我們來(lái)玩一把。
一、概念
赫夫曼樹(shù)里面有幾個(gè)概念，也是非常簡(jiǎn)單的，先來(lái)看下面的圖：
- 節(jié)點(diǎn)的權(quán)： 節(jié)點(diǎn)中紅色部分就是權(quán)，在實(shí)際應(yīng)用中，我們用“字符”出現(xiàn)的次數(shù)作為權(quán)。
- 路徑長(zhǎng)度：可以理解成該節(jié)點(diǎn)到根節(jié)點(diǎn)的層數(shù)，比如：“A”到根節(jié)點(diǎn)的路徑長(zhǎng)度為 3。
- 樹(shù)的路徑長(zhǎng)度：各個(gè)葉子節(jié)點(diǎn)到根節(jié)點(diǎn)的路徑長(zhǎng)度總和，用 WPL 標(biāo)記。
最后我們要討論的的赫夫曼樹(shù)也就是帶權(quán)路徑長(zhǎng)度最小的一棵樹(shù)。
二、構(gòu)建
由于要使 WPL 最短，赫夫曼樹(shù)的構(gòu)建采用自低向上的方式，這里我們采用小根堆來(lái)存放當(dāng)前需要構(gòu)建的各個(gè)節(jié)點(diǎn)，我們的方式是每次從小根堆中取出最小的兩個(gè)節(jié)點(diǎn)，合并后放入堆中，然后繼續(xù)取兩個(gè)最小的節(jié)點(diǎn)，一直到小根堆為空，最后我們采用自底向上構(gòu)建的赫夫曼樹(shù)也就完畢了。
好了，赫夫曼樹(shù)的典型應(yīng)用就是在數(shù)據(jù)壓縮方面，下面我們就要在赫夫曼樹(shù)上面放入赫夫曼編碼了，我們知道普通的 ASCII 碼是采用等長(zhǎng)編碼的，即每個(gè)字符都采用 2 個(gè)字節(jié)，而赫夫曼編碼的思想就是采用不等長(zhǎng)的思路，權(quán)重高的字符靠近根節(jié)點(diǎn)，權(quán)重低的字符遠(yuǎn)離根節(jié)點(diǎn)，標(biāo)記方式為左孩子“0”，右孩子“1”，如下圖。
從圖中我們可以看到各個(gè)字符的赫夫曼編碼了，獲取字符的編碼采用從根往下的方式收集路徑上的‘0,1’，如：
A:110。
B:111。
C:0。
D:10。
最后我們來(lái)比較他們的 WPL 的長(zhǎng)度： ASCII 碼=102+202+402+802=300
赫夫曼碼=103+203+402+801=250
可以看到，赫夫曼碼壓縮了 50 個(gè) 0,1 字符。
三、代碼
1、樹(shù)節(jié)點(diǎn)
我們采用 7 元節(jié)點(diǎn)，其中 parent 方便我們?cè)?DFS 的時(shí)候找到從葉子節(jié)點(diǎn)到根節(jié)點(diǎn)的路徑上的赫夫曼編碼。
#region 赫夫曼節(jié)點(diǎn)
/// <summary>
/// 赫夫曼節(jié)點(diǎn)
/// </summary>
public class Node
{
/// <summary>
/// 左孩子
/// </summary>
public Node left;
/// <summary>
/// 右孩子
/// </summary>
public Node right;
/// <summary>
/// 父節(jié)點(diǎn)
/// </summary>
public Node parent;
/// <summary>
/// 節(jié)點(diǎn)字符
/// </summary>
public char c;
/// <summary>
/// 節(jié)點(diǎn)權(quán)重
/// </summary>
public int weight;
//赫夫曼“0"or“1"
public char huffmancode;
/// <summary>
/// 標(biāo)記是否為葉子節(jié)點(diǎn)
/// </summary>
public bool isLeaf;
}
#endregion
2、構(gòu)建赫夫曼樹(shù)（Build）
上面也說(shuō)了，構(gòu)建赫夫曼編碼樹(shù)我們采用小根堆的形式構(gòu)建，構(gòu)建完后，我們采用 DFS 的方式統(tǒng)計(jì)各個(gè)字符的編碼，復(fù)雜度為 N*logN。
#region 構(gòu)建赫夫曼樹(shù)
/// <summary>
/// 構(gòu)建赫夫曼樹(shù)
/// </summary>
public void Build()
{
//構(gòu)建
while (queue.Count() > 0)
{
//如果只有一個(gè)節(jié)點(diǎn)，則說(shuō)明已經(jīng)到根節(jié)點(diǎn)了
if (queue.Count() == 1)
{
root = queue.Dequeue().t;
break;
}
//節(jié)點(diǎn)1
var node1 = queue.Dequeue();
//節(jié)點(diǎn)2
var node2 = queue.Dequeue();
//標(biāo)記左孩子
node1.t.huffmancode = '0';
//標(biāo)記為右孩子
node2.t.huffmancode = '1';
//判斷當(dāng)前節(jié)點(diǎn)是否為葉子節(jié)點(diǎn),hufuman無(wú)度為1點(diǎn)節(jié)點(diǎn)（方便計(jì)算huffman編碼）
if (node1.t.left == null)
node1.t.isLeaf = true;
if (node2.t.left == null)
node2.t.isLeaf = true;
//父節(jié)點(diǎn)
root = new Node();
root.left = node1.t;
root.right = node2.t;
root.weight = node1.t.weight + node2.t.weight;
//當(dāng)前節(jié)點(diǎn)為根節(jié)點(diǎn)
node1.t.parent = node2.t.parent = root;
//將當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)入隊(duì)列
queue.Eequeue(root, root.weight);
}
//深度優(yōu)先統(tǒng)計(jì)各個(gè)字符的編碼
DFS(root);
}
#endregion
3、編碼(Encode,Decode)
樹(shù)構(gòu)建起來(lái)后，我會(huì)用字典來(lái)保存字符和”赫夫曼編碼“的對(duì)應(yīng)表，然后拿著明文或者密文對(duì)著編碼表翻譯就行了， 復(fù)雜度 O(N)。
#region 赫夫曼編碼
/// <summary>
/// 赫夫曼編碼
/// </summary>
/// <returns></returns>
public string Encode()
{
StringBuilder sb = new StringBuilder();
foreach (var item in word)
{
sb.Append(huffmanEncode[item]);
}
return sb.ToString();
}
#endregion
#region 赫夫曼解碼
/// <summary>
/// 赫夫曼解碼
/// </summary>
/// <returns></returns>
public string Decode(string str)
{
StringBuilder decode = new StringBuilder();
string temp = string.Empty;
for (int i = 0; i < str.Length; i++)
{
temp += str[i].ToString();
//如果包含 O(N)時(shí)間
if (huffmanDecode.ContainsKey(temp))
{
decode.Append(huffmanDecode[temp]);
temp = string.Empty;
}
}
return decode.ToString();
}
#endregion
最后我們做個(gè)例子，壓縮 9M 的文件，看看到底能壓縮多少？
public static void Main()
{
StringBuilder sb = new StringBuilder();
for (int i = 0; i < 1 * 10000; i++)
{
sb.Append("人民網(wǎng)北京12月8日電 （記者 宋心蕊） 北京時(shí)間8日晚的央視《新聞聯(lián)播》節(jié)目出現(xiàn)了直播失誤。上一條新聞尚未播放完畢時(shí)，播就將畫(huà)面切換回了演播間，主播李梓萌開(kāi)始播報(bào)下一條新聞，導(dǎo)致兩條新聞出現(xiàn)了“混音”播出。央視新聞官方微博賬號(hào)在21點(diǎn)09分發(fā)布了一條致歉微博：【致歉】今晚《新聞聯(lián)播》因?qū)РT口令失誤，導(dǎo)致畫(huà)面切換錯(cuò)誤，特此向觀眾朋友表示歉意。央視特約評(píng)論員楊禹在個(gè)人微博中寫(xiě)道：今晚《新聞聯(lián)播》出了個(gè)切換錯(cuò)誤，@央視新聞 及時(shí)做了誠(chéng)懇道歉。聯(lián)播一直奉行“金標(biāo)準(zhǔn)”，壓力源自全社會(huì)的高要求。其實(shí)報(bào)紙亦都有“勘誤”一欄，坦誠(chéng)糾錯(cuò)與道歉?！缎侣劼?lián)播》是中國(guó)影響力最大的電視新聞節(jié)目。它有不可替代的符號(hào)感，它有失誤，更有悄然的進(jìn)步。新的改進(jìn)正在或即將發(fā)生，不妨期待");
}
File.WriteAllText(Environment.CurrentDirectory + "http://1.txt", sb.ToString());
Huffman huffman = new Huffman(sb.ToString());
Stopwatch watch = Stopwatch.StartNew();
huffman.Build();
watch.Stop();
Console.WriteLine("構(gòu)建赫夫曼樹(shù)耗費(fèi):{0}", watch.ElapsedMilliseconds);
//將8位二進(jìn)制轉(zhuǎn)化為ascII碼
var s = huffman.Encode();
var remain = s.Length % 8;
List<char> list = new List<char>();
var start = 0;
for (int i = 8; i < s.Length; i = i + 8)
{
list.Add((char)Convert.ToInt32(s.Substring(i - 8, 8), 2));
start = i;
}
var result = new String(list.ToArray());
//當(dāng)字符編碼不足8位時(shí)， 用‘艸'來(lái)標(biāo)記，然后拿出'擦‘以后的所有0,1即可
result += "艸" + s.Substring(start);
File.WriteAllText(Environment.CurrentDirectory + "http://2.txt", result);
Console.WriteLine("壓縮完畢！");
Console.Read();
//解碼
var str = File.ReadAllText(Environment.CurrentDirectory + "http://2.txt");
sb.Clear();
for (int i = 0; i < str.Length; i++)
{
int ua = (int)str[i];
//說(shuō)明已經(jīng)取完畢了 用'艸'來(lái)做標(biāo)記
if (ua == 33401)
sb.Append(str.Substring(i));
else
sb.Append(Convert.ToString(ua, 2).PadLeft(8, '0'));
}
var sss = huffman.Decode(sb.ToString());
Console.Read();
}
看看，將 9M 的文件壓縮到了 4M。
主程序：
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;
using System.Threading;
using System.IO;
namespace ConsoleApplication2
{
public class Program
{
public static void Main()
{
StringBuilder sb = new StringBuilder();
for (int i = 0; i < 1 * 10000; i++)
{
sb.Append("人民網(wǎng)北京12月8日電 （記者 宋心蕊） 北京時(shí)間8日晚的央視《新聞聯(lián)播》節(jié)目出現(xiàn)了直播失誤。上一條新聞尚未播放完畢時(shí)，播就將畫(huà)面切換回了演播間，主播李梓萌開(kāi)始播報(bào)下一條新聞，導(dǎo)致兩條新聞出現(xiàn)了“混音”播出。央視新聞官方微博賬號(hào)在21點(diǎn)09分發(fā)布了一條致歉微博：【致歉】今晚《新聞聯(lián)播》因?qū)РT口令失誤，導(dǎo)致畫(huà)面切換錯(cuò)誤，特此向觀眾朋友表示歉意。央視特約評(píng)論員楊禹在個(gè)人微博中寫(xiě)道：今晚《新聞聯(lián)播》出了個(gè)切換錯(cuò)誤，@央視新聞 及時(shí)做了誠(chéng)懇道歉。聯(lián)播一直奉行“金標(biāo)準(zhǔn)”，壓力源自全社會(huì)的高要求。其實(shí)報(bào)紙亦都有“勘誤”一欄，坦誠(chéng)糾錯(cuò)與道歉。《新聞聯(lián)播》是中國(guó)影響力最大的電視新聞節(jié)目。它有不可替代的符號(hào)感，它有失誤，更有悄然的進(jìn)步。新的改進(jìn)正在或即將發(fā)生，不妨期待");
}
File.WriteAllText(Environment.CurrentDirectory + "http://1.txt", sb.ToString());
Huffman huffman = new Huffman(sb.ToString());
Stopwatch watch = Stopwatch.StartNew();
huffman.Build();
watch.Stop();
Console.WriteLine("構(gòu)建赫夫曼樹(shù)耗費(fèi):{0}", watch.ElapsedMilliseconds);
//將8位二進(jìn)制轉(zhuǎn)化為ascII碼
var s = huffman.Encode();
var remain = s.Length % 8;
List<char> list = new List<char>();
var start = 0;
for (int i = 8; i < s.Length; i = i + 8)
{
list.Add((char)Convert.ToInt32(s.Substring(i - 8, 8), 2));
start = i;
}
var result = new String(list.ToArray());
//當(dāng)字符編碼不足8位時(shí)， 用‘艸'來(lái)標(biāo)記，然后拿出'擦‘以后的所有0,1即可
result += "艸" + s.Substring(start);
File.WriteAllText(Environment.CurrentDirectory + "http://2.txt", result);
Console.WriteLine("壓縮完畢！");
Console.Read();
//解碼
var str = File.ReadAllText(Environment.CurrentDirectory + "http://2.txt");
sb.Clear();
for (int i = 0; i < str.Length; i++)
{
int ua = (int)str[i];
//說(shuō)明已經(jīng)取完畢了 用'艸'來(lái)做標(biāo)記
if (ua == 33401)
sb.Append(str.Substring(i));
else
sb.Append(Convert.ToString(ua, 2).PadLeft(8, '0'));
}
var sss = huffman.Decode(sb.ToString());
Console.Read();
}
}
public class Huffman
{
#region 赫夫曼節(jié)點(diǎn)
/// <summary>
/// 赫夫曼節(jié)點(diǎn)
/// </summary>
public class Node
{
/// <summary>
/// 左孩子
/// </summary>
public Node left;
/// <summary>
/// 右孩子
/// </summary>
public Node right;
/// <summary>
/// 父節(jié)點(diǎn)
/// </summary>
public Node parent;
/// <summary>
/// 節(jié)點(diǎn)字符
/// </summary>
public char c;
/// <summary>
/// 節(jié)點(diǎn)權(quán)重
/// </summary>
public int weight;
//赫夫曼“0"or“1"
public char huffmancode;
/// <summary>
/// 標(biāo)記是否為葉子節(jié)點(diǎn)
/// </summary>
public bool isLeaf;
}
#endregion
PriorityQueue<Node> queue = new PriorityQueue<Node>();
/// <summary>
/// 編碼對(duì)應(yīng)表（加速用）
/// </summary>
Dictionary<char, string> huffmanEncode = new Dictionary<char, string>();
/// <summary>
/// 解碼對(duì)應(yīng)表（加速用）
/// </summary>
Dictionary<string, char> huffmanDecode = new Dictionary<string, char>();
/// <summary>
/// 明文
/// </summary>
string word = string.Empty;
public Node root = new Node();
public Huffman(string str)
{
this.word = str;
Dictionary<char, int> dic = new Dictionary<char, int>();
foreach (var s in str)
{
if (dic.ContainsKey(s))
dic[s] += 1;
else
dic[s] = 1;
}
foreach (var item in dic.Keys)
{
var node = new Node()
{
c = item,
weight = dic[item]
};
//入隊(duì)
queue.Eequeue(node, dic[item]);
}
}
#region 構(gòu)建赫夫曼樹(shù)
/// <summary>
/// 構(gòu)建赫夫曼樹(shù)
/// </summary>
public void Build()
{
//構(gòu)建
while (queue.Count() > 0)
{
//如果只有一個(gè)節(jié)點(diǎn)，則說(shuō)明已經(jīng)到根節(jié)點(diǎn)了
if (queue.Count() == 1)
{
root = queue.Dequeue().t;
break;
}
//節(jié)點(diǎn)1
var node1 = queue.Dequeue();
//節(jié)點(diǎn)2
var node2 = queue.Dequeue();
//標(biāo)記左孩子
node1.t.huffmancode = '0';
//標(biāo)記為右孩子
node2.t.huffmancode = '1';
//判斷當(dāng)前節(jié)點(diǎn)是否為葉子節(jié)點(diǎn),hufuman無(wú)度為1點(diǎn)節(jié)點(diǎn)（方便計(jì)算huffman編碼）
if (node1.t.left == null)
node1.t.isLeaf = true;
if (node2.t.left == null)
node2.t.isLeaf = true;
//父節(jié)點(diǎn)
root = new Node();
root.left = node1.t;
root.right = node2.t;
root.weight = node1.t.weight + node2.t.weight;
//當(dāng)前節(jié)點(diǎn)為根節(jié)點(diǎn)
node1.t.parent = node2.t.parent = root;
//將當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)入隊(duì)列
queue.Eequeue(root, root.weight);
}
//深度優(yōu)先統(tǒng)計(jì)各個(gè)字符的編碼
DFS(root);
}
#endregion
#region 赫夫曼編碼
/// <summary>
/// 赫夫曼編碼
/// </summary>
/// <returns></returns>
public string Encode()
{
StringBuilder sb = new StringBuilder();
foreach (var item in word)
{
sb.Append(huffmanEncode[item]);
}
return sb.ToString();
}
#endregion
#region 赫夫曼解碼
/// <summary>
/// 赫夫曼解碼
/// </summary>
/// <returns></returns>
public string Decode(string str)
{
StringBuilder decode = new StringBuilder();
string temp = string.Empty;
for (int i = 0; i < str.Length; i++)
{
temp += str[i].ToString();
//如果包含 O(N)時(shí)間
if (huffmanDecode.ContainsKey(temp))
{
decode.Append(huffmanDecode[temp]);
temp = string.Empty;
}
}
return decode.ToString();
}
#endregion
#region 深度優(yōu)先遍歷子節(jié)點(diǎn)，統(tǒng)計(jì)各個(gè)節(jié)點(diǎn)的赫夫曼編碼
/// <summary>
/// 深度優(yōu)先遍歷子節(jié)點(diǎn)，統(tǒng)計(jì)各個(gè)節(jié)點(diǎn)的赫夫曼編碼
/// </summary>
/// <returns></returns>
public void DFS(Node node)
{
if (node == null)
return;
//遍歷左子樹(shù)
DFS(node.left);
//遍歷右子樹(shù)
DFS(node.right);
//如果當(dāng)前葉節(jié)點(diǎn)
if (node.isLeaf)
{
string code = string.Empty;
var temp = node;
//回溯的找父親節(jié)點(diǎn)的huffmancode LgN 的時(shí)間
while (temp.parent != null)
{
//注意，這里最后形成的 “反過(guò)來(lái)的編碼”
code += temp.huffmancode;
temp = temp.parent;
}
var codetemp = new String(code.Reverse().ToArray());
huffmanEncode.Add(node.c, codetemp);
huffmanDecode.Add(codetemp, node.c);
}
}
#endregion
}
}
小根堆：
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;
using System.Threading;
using System.IO;
namespace ConsoleApplication2
{
public class PriorityQueue<T> where T : class
{
/// <summary>
/// 定義一個(gè)數(shù)組來(lái)存放節(jié)點(diǎn)
/// </summary>
private List<HeapNode> nodeList = new List<HeapNode>();
#region 堆節(jié)點(diǎn)定義
/// <summary>
/// 堆節(jié)點(diǎn)定義
/// </summary>
public class HeapNode
{
/// <summary>
/// 實(shí)體數(shù)據(jù)
/// </summary>
public T t { get; set; }
/// <summary>
/// 優(yōu)先級(jí)別 1-10個(gè)級(jí)別 (優(yōu)先級(jí)別遞增)
/// </summary>
public int level { get; set; }
public HeapNode(T t, int level)
{
this.t = t;
this.level = level;
}
public HeapNode() { }
}
#endregion
#region 添加操作
/// <summary>
/// 添加操作
/// </summary>
public void Eequeue(T t, int level = 1)
{
//將當(dāng)前節(jié)點(diǎn)追加到堆尾
nodeList.Add(new HeapNode(t, level));
//如果只有一個(gè)節(jié)點(diǎn)，則不需要進(jìn)行篩操作
if (nodeList.Count == 1)
return;
//獲取最后一個(gè)非葉子節(jié)點(diǎn)
int parent = nodeList.Count / 2 - 1;
//堆調(diào)整
UpHeapAdjust(nodeList, parent);
}
#endregion
#region 對(duì)堆進(jìn)行上濾操作，使得滿足堆性質(zhì)
/// <summary>
/// 對(duì)堆進(jìn)行上濾操作，使得滿足堆性質(zhì)
/// </summary>
/// <param name="nodeList"></param>
/// <param name="index">非葉子節(jié)點(diǎn)的之后指針（這里要注意：我們
/// 的篩操作時(shí)針對(duì)非葉節(jié)點(diǎn)的）
/// </param>
public void UpHeapAdjust(List<HeapNode> nodeList, int parent)
{
while (parent >= 0)
{
//當(dāng)前index節(jié)點(diǎn)的左孩子
var left = 2 * parent + 1;
//當(dāng)前index節(jié)點(diǎn)的右孩子
var right = left + 1;
//parent子節(jié)點(diǎn)中最大的孩子節(jié)點(diǎn)，方便于parent進(jìn)行比較
//默認(rèn)為left節(jié)點(diǎn)
var min = left;
//判斷當(dāng)前節(jié)點(diǎn)是否有右孩子
if (right < nodeList.Count)
{
//判斷parent要比較的最大子節(jié)點(diǎn)
min = nodeList[left].level < nodeList[right].level ? left : right;
}
//如果parent節(jié)點(diǎn)大于它的某個(gè)子節(jié)點(diǎn)的話，此時(shí)篩操作
if (nodeList[parent].level > nodeList[min].level)
{
//子節(jié)點(diǎn)和父節(jié)點(diǎn)進(jìn)行交換操作
var temp = nodeList[parent];
nodeList[parent] = nodeList[min];
nodeList[min] = temp;
//繼續(xù)進(jìn)行更上一層的過(guò)濾
parent = (int)Math.Ceiling(parent / 2d) - 1;
}
else
{
break;
}
}
}
#endregion
#region 優(yōu)先隊(duì)列的出隊(duì)操作
/// <summary>
/// 優(yōu)先隊(duì)列的出隊(duì)操作
/// </summary>
/// <returns></returns>
public HeapNode Dequeue()
{
if (nodeList.Count == 0)
return null;
//出隊(duì)列操作，彈出數(shù)據(jù)頭元素
var pop = nodeList[0];
//用尾元素填充頭元素
nodeList[0] = nodeList[nodeList.Count - 1];
//刪除尾節(jié)點(diǎn)
nodeList.RemoveAt(nodeList.Count - 1);
//然后從根節(jié)點(diǎn)下濾堆
DownHeapAdjust(nodeList, 0);
return pop;
}
#endregion
#region 對(duì)堆進(jìn)行下濾操作，使得滿足堆性質(zhì)
/// <summary>
/// 對(duì)堆進(jìn)行下濾操作，使得滿足堆性質(zhì)
/// </summary>
/// <param name="nodeList"></param>
/// <param name="index">非葉子節(jié)點(diǎn)的之后指針（這里要注意：我們
/// 的篩操作時(shí)針對(duì)非葉節(jié)點(diǎn)的）
/// </param>
public void DownHeapAdjust(List<HeapNode> nodeList, int parent)
{
while (2 * parent + 1 < nodeList.Count)
{
//當(dāng)前index節(jié)點(diǎn)的左孩子
var left = 2 * parent + 1;
//當(dāng)前index節(jié)點(diǎn)的右孩子
var right = left + 1;
//parent子節(jié)點(diǎn)中最大的孩子節(jié)點(diǎn)，方便于parent進(jìn)行比較
//默認(rèn)為left節(jié)點(diǎn)
var min = left;
//判斷當(dāng)前節(jié)點(diǎn)是否有右孩子
if (right < nodeList.Count)
{
//判斷parent要比較的最大子節(jié)點(diǎn)
min = nodeList[left].level < nodeList[right].level ? left : right;
}
//如果parent節(jié)點(diǎn)小于它的某個(gè)子節(jié)點(diǎn)的話，此時(shí)篩操作
if (nodeList[parent].level > nodeList[min].level)
{
//子節(jié)點(diǎn)和父節(jié)點(diǎn)進(jìn)行交換操作
var temp = nodeList[parent];
nodeList[parent] = nodeList[min];
nodeList[min] = temp;
//繼續(xù)進(jìn)行更下一層的過(guò)濾
parent = min;
}
else
{
break;
}
}
}
#endregion
#region 獲取元素并下降到指定的level級(jí)別
/// <summary>
/// 獲取元素并下降到指定的level級(jí)別
/// </summary>
/// <returns></returns>
public HeapNode GetAndDownPriority(int level)
{
if (nodeList.Count == 0)
return null;
//獲取頭元素
var pop = nodeList[0];
//設(shè)置指定優(yōu)先級(jí)（如果為 MinValue 則為 -- 操作）
nodeList[0].level = level == int.MinValue ? --nodeList[0].level : level;
//下濾堆
DownHeapAdjust(nodeList, 0);
return nodeList[0];
}
#endregion
#region 獲取元素并下降優(yōu)先級(jí)
/// <summary>
/// 獲取元素并下降優(yōu)先級(jí)
/// </summary>
/// <returns></returns>
public HeapNode GetAndDownPriority()
{
//下降一個(gè)優(yōu)先級(jí)
return GetAndDownPriority(int.MinValue);
}
#endregion
#region 返回當(dāng)前優(yōu)先隊(duì)列中的元素個(gè)數(shù)
/// <summary>
/// 返回當(dāng)前優(yōu)先隊(duì)列中的元素個(gè)數(shù)
/// </summary>
/// <returns></returns>
public int Count()
{
return nodeList.Count;
}
#endregion
}
}
到此這篇關(guān)于基于C#實(shí)現(xiàn)哈夫曼樹(shù)算法的文章就介紹到這了,更多相關(guān)C#哈夫曼樹(shù)算法內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
洗牌算法的要求是這樣的:將N個(gè)數(shù)亂序后輸出.由于和撲克牌的洗牌過(guò)程比較相似所以我也就稱為洗牌算法了.很多地方都不自覺(jué)的需要這個(gè)算法的支持.也可以將這個(gè)算法擴(kuò)展為從N個(gè)數(shù)中取出M個(gè)不重復(fù)的數(shù)(0<M<=N).今天我們看下如何用C#來(lái)實(shí)現(xiàn)2015-03-03
C#使用ADO.Net連接數(shù)據(jù)庫(kù)與DbProviderFactory實(shí)現(xiàn)多數(shù)據(jù)庫(kù)訪問(wèn)
這篇文章介紹了C#使用ADO.Net連接數(shù)據(jù)庫(kù)與DbProviderFactory實(shí)現(xiàn)多數(shù)據(jù)庫(kù)訪問(wèn)的方法，文中通過(guò)示例代碼介紹的非常詳細(xì)。對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2022-05-05
這篇文章主要為大家詳細(xì)介紹了C#實(shí)現(xiàn)異步編程的方法，什么是異步，如何實(shí)現(xiàn)異步編程，感興趣的小伙伴們可以參考一下2017-07-07
C#使用WebSocket實(shí)現(xiàn)聊天室功能
這篇文章主要為大家詳細(xì)介紹了C#使用WebSocket實(shí)現(xiàn)聊天室功能，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-02-02
c#中WinForm使用OpencvSharp4實(shí)現(xiàn)簡(jiǎn)易抓邊
本文主要介紹了c#中WinForm使用OpencvSharp4實(shí)現(xiàn)簡(jiǎn)易抓邊，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2022-05-05
就是一個(gè)簡(jiǎn)單的例子, 調(diào)用系統(tǒng)的 dwm 去重繪窗口. 只能在 Vista 和 7 之后才可以, 并且要確保已經(jīng)開(kāi)啟主題服務(wù)等等, 總之不是非常實(shí)用, 好玩而已2011-05-05
C#連接ClickHouse數(shù)據(jù)庫(kù)的步驟指南
在 C# 中連接 ClickHouse 數(shù)據(jù)庫(kù),您可以使用 ClickHouse.Client 庫(kù),這個(gè)庫(kù)提供了對(duì) ClickHouse 數(shù)據(jù)庫(kù)的高效訪問(wèn),以下是詳細(xì)的步驟指南,幫助您在 C# 項(xiàng)目中連接和操作 ClickHouse 數(shù)據(jù)庫(kù),需要的朋友可以參考下2024-12-12
這篇文章主要介紹了C#.Net ArrayList的使用方法,使用動(dòng)態(tài)數(shù)組的優(yōu)點(diǎn)是可以根據(jù)用戶需要，有效利用存儲(chǔ)空間，需要的朋友可以參考下2015-10-10
c# WinForm 窗體之間傳值的幾種方式(小結(jié))
這篇文章主要介紹了WinForm 窗體之間傳值的幾種方式(小結(jié))，小編覺(jué)得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2018-09-09
這篇文章主要為大家詳細(xì)介紹了在C#中如何實(shí)現(xiàn)手動(dòng)改變自制窗體的大小,文中的示例代碼講解詳細(xì),感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下2024-03-03