admin管理员组文章数量:1623796
先决条件: 贪婪算法 | (霍夫曼编码)、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)
版权声明:本文标题:c++ 使用优先级队列的霍夫曼编码(Huffman Coding using Priority Queue) 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://m.elefans.com/dianzi/1728895918a1178404.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论