#include <iostream>
#include <queue>
#include <unordered_map>
using namespace std;
struct Node {
char data;
unsigned freq;
Node left, right;
Node(char data, unsigned freq, Node left = nullptr, Node right = nullptr)
: data(data), freq(freq), left(left), right(right) {}
};
struct compare {
bool operator()(Node l, Node r) {
return (l->freq > r->freq);
}
};
void printCodes(Node* root, string str, unordered_map<char, string>& huffmanCodes) {
if (!root)
return;
if (root->data != '$')
huffmanCodes[root->data] = str;
printCodes(root->left, str + "0", huffmanCodes);
printCodes(root->right, str + "1", huffmanCodes);
}
void buildHuffmanTree(string text) {
unordered_map<char, unsigned> freq;
for (char ch : text)
freq[ch]++;
priority_queue<Node, vector<Node>, compare> minHeap;
for (auto pair : freq)
minHeap.push(new Node(pair.first, pair.second));
while (minHeap.size() != 1) {
Node* left = minHeap.top();
minHeap.pop();
Node* right = minHeap.top();
minHeap.pop();
Node* top = new Node('$', left->freq + right->freq, left, right);
minHeap.push(top);
}
Node* root = minHeap.top();
unordered_map<char, string> huffmanCodes;
printCodes(root, "", huffmanCodes);
cout << "Huffman Codes are:\n";
for (auto pair : huffmanCodes)
cout << pair.first << " " << pair.second << "\n";
}
int main() {
string text = "hello world";
buildHuffmanTree(text);
return 0;
}