使用二叉堆构建霍夫曼树

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{&nbsp; &nbsp; internal HuffmanTreeNode rootNode;&nbsp; &nbsp; private Dictionary<char, int> dictFrequencies;&nbsp; &nbsp; HuffmanPriorityQueue huffmanPriorityQueue;&nbsp; &nbsp; internal void Build(string input)&nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; dictFrequencies = input.GroupBy(x => x).ToDictionary(k => k.Key, v => v.Count());&nbsp; &nbsp; &nbsp; &nbsp; huffmanPriorityQueue = new HuffmanPriorityQueue(dictFrequencies.Count);&nbsp; &nbsp; &nbsp; &nbsp; foreach (var item in dictFrequencies)&nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; huffmanPriorityQueue.Push(new HuffmanTreeNode { Symbol = item.Key, Frequency = item.Value, Left = null, Right = null });&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; while(huffmanPriorityQueue.Count() >= 2)&nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; HuffmanTreeNode leftNode = huffmanPriorityQueue.Pop();&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; HuffmanTreeNode rightNode = huffmanPriorityQueue.Pop();&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; HuffmanTreeNode parentNode = new HuffmanTreeNode&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; Frequency = leftNode.Frequency + rightNode.Frequency,&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; Symbol = '*',&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; Left = leftNode,&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; Right = rightNode&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; };&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; this.rootNode = parentNode;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; huffmanPriorityQueue.Push(parentNode);&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }internal class HuffmanPriorityQueue{&nbsp; &nbsp; HuffmanTreeNode[] items;&nbsp; &nbsp; int top = 0;&nbsp; &nbsp; public HuffmanPriorityQueue(int size)&nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; items = new HuffmanTreeNode[size + 1];&nbsp; &nbsp; }&nbsp; &nbsp; internal void Push(HuffmanTreeNode node)&nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; int i = ++top;&nbsp; &nbsp; &nbsp; &nbsp; while (i > 1 && items[i / 2].Frequency > node.Frequency)&nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; items[i] = items[i / 2];&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; i = i / 2;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; items[i] = node;&nbsp; &nbsp; }&nbsp; &nbsp; internal HuffmanTreeNode Pop()&nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; HuffmanTreeNode data = items[1];&nbsp; &nbsp; &nbsp; &nbsp; items[1] = items[top];&nbsp; &nbsp; &nbsp; &nbsp; items[top--] = null;&nbsp; &nbsp; &nbsp; &nbsp; int i = 1;&nbsp; &nbsp; &nbsp; &nbsp; int j = i * 2;&nbsp; &nbsp; &nbsp; &nbsp; while (j <= top)&nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if ((j + 1) <= top && items[j + 1].Frequency < items[j].Frequency)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; j += 1;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (items[j].Frequency < items[i].Frequency)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; HuffmanTreeNode temp = items[j];&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; items[j] = items[i];&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; items[i] = temp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; i = j;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; j = i * 2;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; else&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; break;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; return data;&nbsp; &nbsp; }&nbsp; &nbsp; internal int Count()&nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; return top;&nbsp; &nbsp; }}internal class HuffmanTreeNode{&nbsp; &nbsp; internal char Symbol { get; set; }&nbsp; &nbsp; internal int Frequency { get; set; }&nbsp; &nbsp; internal HuffmanTreeNode Right { get; set; }&nbsp; &nbsp; internal HuffmanTreeNode Left { get; set; }}