使用最小优先级队列的霍夫曼编码

Question

在这个问题中，我需要打印所有数据的霍夫曼代码。但是对于下面给定的测试用例，我得到了不同的输出。

输入

8

i j k l m n o p

5 9 12 13 16 45 55 70

在哪里

第一行输入字母个数

第二行输入字母

第三行输入字母出现的频率

预期输出

n: 00

k: 0100

l: 0101

我：01100

j: 01101

米: 0111

o: 10

p: 11

我的输出

n: 00

o: 01

k: 1000

l: 1001

我：10100

j: 10101

米: 1011

p: 11

我的代码

#include<bits/stdc++.h>
using namespace std;

struct Node {
    char data;
    int freq;
    Node *left, *right;
    Node(char x, int y): data(x), freq(y), left(NULL), right(NULL) {}
};

struct compare {
    bool operator()(Node *l, Node*r) {
        return l->freq > r->freq;
    }
};

void display(Node *p, string str) {
    if(p) {
        if(p->data != '$')
            cout << p->data << ": " << str << "\n";
        display(p->left, str + "0");
        display(p->right, str + "1");
    }
}

void huffmanCodes(char data[], int fr[], int n) {
    priority_queue<Node*, vector<Node*>, compare > pq;
    for(int i=0;i<n;i++)
        pq.push(new Node(data[i], fr[i]));
    while(pq.size() != 1) {
        Node *l = pq.top();
        pq.pop();
        Node *r = pq.top();
        pq.pop();
        Node *t = new Node('$', l->freq + r->freq);
        t->left = l;
        t->right = r; 
        pq.push(t);
    }
    display(pq.top(), "");
}

int main() {
    int n;
    cin >> n;
    char data[n];
    int freq[n];
    for(auto &x: data) cin >> x;
    for(auto &x: freq) cin >> x;
    huffmanCodes(data, freq, n);
}

Answer 1

对于一组特定的频率，不一定只有一个正确的霍夫曼树。如果我们看看你的，我们最初有以下分布

i:5 j:9 k:12 l:13 m:16 n:45 o:55 p:70

结合我们得到的两个最小值（按频率排序）

(ij):14 m:16 (kl):25 n:45 o:55 p:70

再一次，结合我们得到的两个最小值

(kl):25 (ij)(m):30 o:55 p:70

之后，我们得到

n:45 (kl)((ij)(m)):55 o:55 p:70

现在我们有两个具有相同频率 (55) 的条目，因此我们可以将 n 与 (kl)((ij)(m)) 或 o 组合起来形成一个新节点 - 两者都会产生有效的霍夫曼树，两者都保证在代码大小方面是最佳的，因此我们可以选择其中之一，优先级队列如何实现的详细信息将决定在您的情况下实际选择哪一个。

只要对编码器和解码器使用相同的策略，这两种方式都可以正常工作。

Answer 2

只是添加到 500 的正确答案中，根据所做的选择，您可以获得这些树中的任何一个，它们都是有效且最佳的：

顺便说一下，由于您还显示了位分配，因此对于这两棵树的 each，有 128 种方法可以将代码分配给符号。您可以将每个分支分别设为左侧 0 和右侧 1，或者左侧 1 和右侧 0。所以实际上有 256 种不同的方法可以为这些频率制作有效的霍夫曼代码。

使用最小优先级队列的霍夫曼编码

Huffman Coding using min priority queue

c++

huffman-code