Advertisement
Josif_tepe

Untitled

Mar 24th, 2024
482
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.49 KB | None | 0 0
  1. #include <iostream>
  2. #include <queue>
  3. using namespace std;
  4.  
  5. struct node {
  6.     char value;
  7.     int freq;
  8.    
  9.     node * left,  * right;
  10.    
  11.     node(char _value, int _freq) {
  12.         value = _value;
  13.         freq = _freq;
  14.         left = NULL;
  15.         right = NULL;
  16.     }
  17. };
  18. struct cmp {
  19.     bool operator() (node * n1, node * n2) {
  20.         return (n1->freq > n2->freq);
  21.     }
  22. };
  23. void dfs(node * root, string s) {
  24.     if(!root) {
  25.         return;
  26.     }
  27.     if(root->value != '#') {
  28.         cout << root-> value << ": " << s << endl;
  29.     }
  30.     dfs(root->left, s + "0");
  31.     dfs(root->right, s + "1");
  32. }
  33. void huffman_coding(vector<char> chars, vector<int> freq) {
  34.     priority_queue<node *, vector<node *>, cmp> pq;
  35.     for(int i = 0; i < (int) chars.size(); i++) {
  36.         pq.push(new node(chars[i], freq[i]));
  37.     }
  38.    
  39.     while(pq.size() > 1) {
  40.         node * left = pq.top();
  41.         pq.pop();
  42.        
  43.         node * right = pq.top();
  44.         pq.pop();
  45.        
  46.         node * root = new node('#', left->freq + right -> freq);
  47.         root->left = left;
  48.         root->right = right;
  49.         pq.push(root);
  50.     }
  51.    
  52.     dfs(pq.top(), "");
  53. }
  54. int main() {
  55.     ios_base::sync_with_stdio(false);
  56.     int n;
  57.     cin >> n;
  58.     vector<char> chars(n);
  59.     vector<int> freq(n);
  60.     for(int i = 0; i < n; i++) {
  61.         cin >> chars[i] >> freq[i];
  62.     }
  63.    
  64.     huffman_coding(chars, freq);
  65.     return 0;
  66. }
  67. /*
  68.  6
  69.  a 5
  70.  b 9
  71.  c 12
  72.  d 13
  73.  e 16
  74.  f 45
  75.  
  76.  **/
  77.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement