Archives
Trending
Support
Login
clear text
XML
Django
JavaScript
MATLAB
C
C++
C#
Python
SQL
Shell
Bash
Markdown
YAML
JSON
HTML
CSS
PHP
Java
Ruby
Go
Rust
Swift
Kotlin
Arduino
TypeScript
Perl
Autohotkey
Lua
SQF
R
Scala
Haskell
Groovy
Dart
Clojure
VB.NET
Objective-C
PowerShell
Bash
CoffeeScript
Verilog
#include
#include
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
chars, vector
freq) { priority_queue
, 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
chars(n); vector
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 **/
Mark as private (unlisted)
for 30 minutes
for 6 hours
for 1 day
for 1 week
for 1 month
for 1 year
everlasting (like CCCP)