ハーバーマンコーディングアルゴリズム


アルゴリズムコードは次のとおりです.
public class HuffmanNode
    {
        public char Char { get; set; }
        public int Frequency { get; set; }
        //        
        internal HuffmanNode LeftChild { get; set; }
        internal HuffmanNode RightChild { get; set; }
        //      
        internal HuffmanNode NextSibling { get; set; }
        public string HuffmanCode {get;set;}
        public HuffmanNode(char Char,int Freq)
        {
            this.Char = Char;
            this.Frequency = Freq;
        }
    }
    public class HuffmanAlgorithms
    {
        /// <summary>
        ///        ,        Nodes  ,      。
        /// </summary>
        /// <param name="Nodes"></param>
        public static void HuffmanCode(HuffmanNode[] Nodes)
        {

            if (Nodes == null || Nodes.Length == 0)
            {
                return;
            }
            #region         
            if (Nodes.Length == 1)
            {
                Nodes[0].HuffmanCode = "0";
                return;
            }
            if (Nodes.Length == 2)
            {
                Nodes[0].HuffmanCode = "0";
                Nodes[1].HuffmanCode = "1";
                return;
            }
            #endregion
            HuffmanNode theHead = null;

            //       ,        O(n^2)
            for (int i = 0; i < Nodes.Length;i++ )
            {
                InsertNode(ref theHead, Nodes[i]);
            }
            //  Huffman ,     ,           (   ).
            HuffmanNode theTmp1 = null;
            HuffmanNode theTmp2 = null;
            theTmp1 = theHead;
            if (theHead != null)
            {
                theTmp2 = theHead.NextSibling;
            }
            //         ,     ,       ,    .O(n*lgn)
            while (theTmp1 != null && theTmp2 != null)
            {
                //                    ,                  .
                HuffmanNode theParent = new HuffmanNode('\0', theTmp1.Frequency + theTmp2.Frequency);
                theParent.LeftChild = theTmp1;
                theParent.RightChild = theTmp2;
                //          ,       .
                theHead = theTmp2.NextSibling;
                //              .
                InsertNode(ref theHead, theParent);
                
                theTmp1 = theHead;
                if (theHead != null)
                {
                    theTmp2 = theHead.NextSibling;
                }
            }
            //            .            .o(n)
            HuffmanCode(theHead, "");
            //     ,      .o(n)
            foreach (var node in Nodes)
            {
                node.LeftChild = null;
                node.NextSibling = null;
                node.RightChild = null;
            }
        }
        /// <summary>
        ///             ,            ,      Nodes   。
        /// </summary>
        /// <param name="ANode"></param>
        /// <param name="StrCode"></param>
        private static void HuffmanCode(HuffmanNode ANode, string StrCode)
        {
            if (ANode != null)
            {
                ANode.HuffmanCode = StrCode;
                if (ANode.LeftChild != null)
                {
                    HuffmanCode(ANode.LeftChild, StrCode + "0");
                }
                if (ANode.RightChild != null)
                {
                    HuffmanCode(ANode.RightChild, StrCode + "1");
                }
            }
        }
        /// <summary>
        ///    Node     AHead  ,     .
        /// </summary>
        /// <param name="AHead"></param>
        /// <param name="Node"></param>
        private static void InsertNode(ref HuffmanNode AHead,HuffmanNode Node)
        {
            HuffmanNode theTmp1 = AHead;
            HuffmanNode theTmp2 = null;
            while (theTmp1 != null && theTmp1.Frequency < Node.Frequency)
            {
                theTmp2 = theTmp1;
                theTmp1 = theTmp1.NextSibling;
            }
            if (theTmp2 == null)
            {
                AHead = Node;
            }
            else
            {
                theTmp2.NextSibling = Node;
             }
            Node.NextSibling = theTmp1;
        }
    }

PS:このアルゴリズムは最小スタックの効率が高く、O(nlgn)では、ここのアルゴリズムはO(n^2)であり、挿入ソートアルゴリズムの時間的複雑さに合致する.