Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <queue>
- using namespace std;
- struct node {
- char value;
- int freq;
- node * left, * right;
- node(char _value, int _freq) {
- value = _value;
- freq = _freq;
- left = NULL;
- right = NULL;
- }
- };
- struct cmp {
- bool operator() (node * n1, node * n2) {
- return (n1->freq > n2->freq);
- }
- };
- void dfs(node * root, string s) {
- if(!root) {
- return;
- }
- if(root->value != '#') {
- cout << root-> value << ": " << s << endl;
- }
- dfs(root->left, s + "0");
- dfs(root->right, s + "1");
- }
- void huffman_coding(vector<char> chars, vector<int> freq) {
- priority_queue<node *, vector<node *>, cmp> pq;
- for(int i = 0; i < (int) chars.size(); i++) {
- pq.push(new node(chars[i], freq[i]));
- }
- while(pq.size() > 1) {
- node * left = pq.top();
- pq.pop();
- node * right = pq.top();
- pq.pop();
- node * root = new node('#', left->freq + right -> freq);
- root->left = left;
- root->right = right;
- pq.push(root);
- }
- dfs(pq.top(), "");
- }
- int main() {
- ios_base::sync_with_stdio(false);
- int n;
- cin >> n;
- vector<char> chars(n);
- vector<int> freq(n);
- for(int i = 0; i < n; i++) {
- cin >> chars[i] >> freq[i];
- }
- huffman_coding(chars, freq);
- return 0;
- }
- /*
- 6
- a 5
- b 9
- c 12
- d 13
- e 16
- f 45
- **/
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement