基于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)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: