c++ 使用优先级队列的霍夫曼编码(Huffman Coding using Priority Queue)

admin管理员组

文章数量:1623789

先决条件： 贪婪算法 |  (霍夫曼编码)、priority_queue::push() 和 C++ STL 中的 priority_queue::pop() 。

贪婪算法 |  (霍夫曼编码)：

C#：https://blog.csdn/hefeng_aspnet/article/details/139259708

JavaScript：https://blog.csdn/hefeng_aspnet/article/details/139259648

python：https://blog.csdn/hefeng_aspnet/article/details/139259563 

java：https://blog.csdn/hefeng_aspnet/article/details/139259501 

c++ STL：https://blog.csdn/hefeng_aspnet/article/details/139259407 

c++：https://blog.csdn/hefeng_aspnet/article/details/139259015 

c语言：https://blog.csdn/hefeng_aspnet/article/details/139257803 

priority_queue::push() 和 C++ STL 中的 priority_queue::pop() ：

https://blog.csdn/hefeng_aspnet/article/details/139408479

        给定一个字符数组 ch[]和每个字符的频率作为freq[] 。任务是使用优先级队列为ch[]中的每个字符找到霍夫曼编码。

例子 

输入： ch[] = { 'a', 'b', 'c', 'd', 'e', 'f' }, freq[] = { 5, 9, 12, 13, 16, 45 } 
输出： 
f 0 
c 100 
d 101 
a 1100 
b 1101 
e 111 

方法： 

    1、将ch[]中所有映射到相应频率freq[]的字符推入优先级队列。
    
    2、要创建哈夫曼树，请从优先级队列中弹出两个节点。
    
    3、将从优先级队列中弹出的两个节点指定为新节点的左子节点和右子节点。
    
    4、将新形成的节点推送到优先级队列中。
    
    5、重复以上所有步骤，直到优先级队列的大小变为 1。
    
    6、遍历哈夫曼树（其根是优先级队列中剩下的唯一节点）以存储哈夫曼代码
    
    7、打印ch[]中每个字符的所有存储的哈夫曼编码。 

下面是上述方法的实现： 

// C++ Program for Huffman Coding
// using Priority Queue
#include <iostream>
#include <queue>
using namespace std;
 
// Maximum Height of Huffman Tree.
#define MAX_SIZE 100
 
class HuffmanTreeNode {
public:
    // Stores character
    char data;
 
    // Stores frequency of
    // the character
    int freq;
 
    // Left child of the
    // current node
    HuffmanTreeNode* left;
 
    // Right child of the
    // current node
    HuffmanTreeNode* right;
 
    // Initializing the
    // current node
    HuffmanTreeNode(char character,
                    int frequency)
    {
        data = character;
        freq = frequency;
        left = right = NULL;
    }
};
 
// Custom comparator class
class Compare {
public:
    bool operator()(HuffmanTreeNode* a,
                    HuffmanTreeNode* b)
    {
        // Defining priority on
        // the basis of frequency
        return a->freq > b->freq;
    }
};
 
// Function to generate Huffman
// Encoding Tree
HuffmanTreeNode* generateTree(priority_queue<HuffmanTreeNode*,
                              vector<HuffmanTreeNode*>,
                                             Compare> pq)
{
 
    // We keep on looping till
    // only one node remains in
    // the Priority Queue
    while (pq.size() != 1) {
 
        // Node which has least
        // frequency
        HuffmanTreeNode* left = pq.top();
 
        // Remove node from
        // Priority Queue
        pq.pop();
 
        // Node which has least
        // frequency
        HuffmanTreeNode* right = pq.top();
 
        // Remove node from
        // Priority Queue
        pq.pop();
 
        // A new node is formed
        // with frequency left->freq
        // + right->freq
 
        // We take data as '$'
        // because we are only
        // concerned with the
        // frequency
        HuffmanTreeNode* node = new HuffmanTreeNode('$',
                                  left->freq + right->freq);
        node->left = left;
        node->right = right;
 
        // Push back node
        // created to the
        // Priority Queue
        pq.push(node);
    }
 
    return pq.top();
}
 
// Function to print the
// huffman code for each
// character.
 
// It uses arr to store the codes
void printCodes(HuffmanTreeNode* root,
                int arr[], int top)
{
    // Assign 0 to the left node
    // and recur
    if (root->left) {
        arr[top] = 0;
        printCodes(root->left,
                   arr, top + 1);
    }
 
    // Assign 1 to the right
    // node and recur
    if (root->right) {
        arr[top] = 1;
        printCodes(root->right, arr, top + 1);
    }
 
    // If this is a leaf node,
    // then we print root->data
 
    // We also print the code
    // for this character from arr
    if (!root->left && !root->right) {
        cout << root->data << " ";
        for (int i = 0; i < top; i++) {
            cout << arr[i];
        }
        cout << endl;
    }
}
 
void HuffmanCodes(char data[],
                  int freq[], int size)
{
 
    // Declaring priority queue
    // using custom comparator
    priority_queue<HuffmanTreeNode*,
                   vector<HuffmanTreeNode*>,
                   Compare>
        pq;
 
    // Populating the priority
    // queue
    for (int i = 0; i < size; i++) {
        HuffmanTreeNode* newNode
            = new HuffmanTreeNode(data[i], freq[i]);
        pq.push(newNode);
    }
 
    // Generate Huffman Encoding
    // Tree and get the root node
    HuffmanTreeNode* root = generateTree(pq);
 
    // Print Huffman Codes
    int arr[MAX_SIZE], top = 0;
    printCodes(root, arr, top);
}
 
// Driver Code
int main()
{
    char data[] = { 'a', 'b', 'c', 'd', 'e', 'f' };
    int freq[] = { 5, 9, 12, 13, 16, 45 };
    int size = sizeof(data) / sizeof(data[0]);
 
    HuffmanCodes(data, freq, size);
    return 0;
}

输出： 
f 0 
c 100 
d 101 
a 1100 
b 1101 
e 111
 

时间复杂度： O（n*logn），其中 n 是唯一字符的数量
辅助空间： O（n）

本文标签： 优先级队列霍夫曼HuffmanPriority