SHARE
TWEET

Untitled

a guest Oct 21st, 2019 81 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. #define INF 1e9
  4.  
  5. using namespace std;
  6.  
  7. // ii is an ordered pair. Use .first and .second to reference the first and
  8. // second element respectively|
  9. typedef pair<int,int> ii;
  10. typedef long long ll;
  11. typedef vector<int> vi;
  12. typedef vector<ii> vii;
  13.  
  14. /*
  15.     Computes for the optimal cost of encoding the given frequencies.
  16.  
  17.     Parameters:
  18.     -n : number of elements to encode
  19.     -f : list of frequencies to encode
  20.  
  21.     Returns a long integer with the optimal encoding length.
  22. */
  23. ll greedy_huffman_encoding(const int &n, const vi &f) {
  24.     // initialize min heap (C++ defaults to max heap, so we have to set
  25.     // greater<ii> as the comparator)
  26.     priority_queue<ii,vii,greater<ii>> pq;
  27.  
  28.     // intitialize adjacency list tree. For all n, allocate a dynamic list.
  29.     vector<vi> adj(n,vi());
  30.  
  31.     // insert all frequencies in the min heap along with the node-id
  32.     for(int i = 0; i < n; i++) {
  33.         pq.push(ii(f[i],i));
  34.     }
  35.  
  36.     // while we have more than one root node
  37.     while(pq.size() > 1) {
  38.         // get the two lowest frequency nodes
  39.         ii t1 = pq.top(); pq.pop();
  40.         ii t2 = pq.top(); pq.pop();
  41.  
  42.         // get id of new node
  43.         int new_node = adj.size();
  44.  
  45.         // allocate new dynamic list for new node in adjacency list
  46.         adj.push_back(vi());
  47.  
  48.         // assign t1 and t2 as children to the new node
  49.         adj[new_node].push_back(t1.second);
  50.         adj[new_node].push_back(t2.second);
  51.  
  52.         // add the new node to min heap with frequency equal to the
  53.         // sum of t1 and t2's frequencies
  54.         pq.push(ii(t1.first + t2.first,new_node));
  55.     }
  56.  
  57.     // initialize depth array for entire tree
  58.     vi depth(adj.size(),INF);
  59.  
  60.     // initialize queue for breadth-first traversal of tree
  61.     queue<int> q;
  62.  
  63.     // the top of the min heap gives the id of the root of the huffman code tree
  64.     q.push(pq.top().second);
  65.  
  66.     // initialize depth of root to zero
  67.     depth[pq.top().second] = 0;
  68.  
  69.     // total bit encoding is initialized to zero
  70.     ll ans = 0LL;
  71.  
  72.     // while there are unexplored nodes
  73.     while(!q.empty()) {
  74.         int u = q.front(); q.pop();
  75.  
  76.         // if within original nodes
  77.         if(u < n) {
  78.             // add the bit encoding of this frequency by multiplying the depth
  79.             // by the frequency
  80.             ans += depth[u] * 1LL * f[u];
  81.         }
  82.  
  83.         // for all children
  84.         for(auto &x : adj[u]) {
  85.             // compute depth of child
  86.             depth[x] = depth[u] + 1;
  87.  
  88.             // add to frontier
  89.             q.push(x);
  90.         }
  91.     }
  92.     return ans;
  93. }
  94.  
  95. int main() {
  96.     int n; // number of characters
  97.     vi freqs; // frequency count of characters
  98.  
  99.     // get input
  100.     scanf("%d",&n);
  101.     freqs.assign(n,0);
  102.     for(int i = 0; i < n; i++) {
  103.         scanf("%d",&freqs[i]);
  104.     }
  105.  
  106.     // print output
  107.     printf("%lld\n",greedy_huffman_encoding(n,freqs));
  108. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top