使用二叉堆构建霍夫曼树

Question

我目前正在尝试编写一个读取文本文件并通过创建 HuffmanTree 对其进行编码的程序。我在优先队列的二叉堆中使用并行数组并跟踪我的霍夫曼树。我知道从堆中取出两分钟，合并它们，然后将它们插回堆中直到只剩下一个的原理，但是我无法将该逻辑/算法转换为代码。这是我的 HuffmanEncode 类：public class HuffmanEncode {    public HuffmanEncode(String in, String out) {        // Implements the Huffman encoding algorithm        // Add private methods and instance variables as needed        int[] freqs = new int[128]; // character counts        char[] chars = new char[128]; //characters        freqs = countFrequencies(in);        HuffmanTree[] trees = new HuffmanTree[128]; //single node trees        for(int i= 0; i < freqs.length; i++) {            chars[i] = (char)i;            trees[i] = new HuffmanTree(chars[i]);        }          BinaryHeap heap = new BinaryHeap(128); // create a binary heap        for(int i = 0; i < 128; i++) {             heap.insert(freqs[i], trees[i]);         }        // STUCK HERE        buildTree(heap);        HuffmanTree root = new HuffmanTree();        // STUCK HERE    }    private void buildTree(BinaryHeap h) {        // grab two smallest        while (h.getSize() > 1) { //repeat until there is only one left            int temp1, temp2;            HuffmanTree t1, t2;            temp1 = h.getMinPriority();            temp2 = h.getMinPriority();            // add their frequency to create new single node tree with char 128            int sum = temp1 + temp2;            HuffmanTree node = new HuffmanTree((char)128);            // insert it back into the heap            h.insert(sum, node);        }    }

Answer 1

当你让新节点插入回堆中时，你需要先将它的左右分支连接到你从堆中拉出的两个节点上。

Answer 2

我已经使用最小堆实现了霍夫曼编码。你可能会从中得到一些想法。

internal class HuffmanTree

{

    internal HuffmanTreeNode rootNode;

    private Dictionary<char, int> dictFrequencies;

    HuffmanPriorityQueue huffmanPriorityQueue;

    internal void Build(string input)

    {

        dictFrequencies = input.GroupBy(x => x).ToDictionary(k => k.Key, v => v.Count());

        huffmanPriorityQueue = new HuffmanPriorityQueue(dictFrequencies.Count);

        foreach (var item in dictFrequencies)

        {

            huffmanPriorityQueue.Push(new HuffmanTreeNode { Symbol = item.Key, Frequency = item.Value, Left = null, Right = null });

        }

        while(huffmanPriorityQueue.Count() >= 2)

        {

            HuffmanTreeNode leftNode = huffmanPriorityQueue.Pop();

            HuffmanTreeNode rightNode = huffmanPriorityQueue.Pop();

            HuffmanTreeNode parentNode = new HuffmanTreeNode

            {

                Frequency = leftNode.Frequency + rightNode.Frequency,

                Symbol = '*',

                Left = leftNode,

                Right = rightNode

            };

            this.rootNode = parentNode;

            huffmanPriorityQueue.Push(parentNode);

        }

    }

internal class HuffmanPriorityQueue

{

    HuffmanTreeNode[] items;

    int top = 0;

    public HuffmanPriorityQueue(int size)

    {

        items = new HuffmanTreeNode[size + 1];

    }

    internal void Push(HuffmanTreeNode node)

    {

        int i = ++top;

        while (i > 1 && items[i / 2].Frequency > node.Frequency)

        {

            items[i] = items[i / 2];

            i = i / 2;

        }

        items[i] = node;

    }

    internal HuffmanTreeNode Pop()

    {

        HuffmanTreeNode data = items[1];

        items[1] = items[top];

        items[top--] = null;

        int i = 1;

        int j = i * 2;

        while (j <= top)

        {

            if ((j + 1) <= top && items[j + 1].Frequency < items[j].Frequency)

            {

                j += 1;

            }

            if (items[j].Frequency < items[i].Frequency)

            {

                HuffmanTreeNode temp = items[j];

                items[j] = items[i];

                items[i] = temp;

                i = j;

                j = i * 2;

            }

            else

                break;

        }

        return data;

    }

    internal int Count()

    {

        return top;

    }

}

internal class HuffmanTreeNode

{

    internal char Symbol { get; set; }

    internal int Frequency { get; set; }

    internal HuffmanTreeNode Right { get; set; }

    internal HuffmanTreeNode Left { get; set; }

}