Problem

   

Huffman Coding

Code

#include <stdio.h>
#include <iostream>
#include <queue>
#include <string>
using namespace std;

const int N = 110;
int n;
int freq[N];
struct Node {
 int val;
 int idx;
 Node *left,*right;
 Node() {
  left = right = NULL;
  idx = -1;
 }
 Node(int v) {
  val = v;
  left = right = NULL;
  idx = -1;
 }

};
struct cmp {
 bool operator() (Node *a,Node *b) {
  return a->val > b->val;
 }
};


priority_queue<Node*,vector<Node*>,cmp> que;

void dfs(Node *root,string pre) {
 if (root == NULL) return;
 if (root->left == NULL && root->right == NULL) {
  cout << root->idx << " " << pre << endl;
  return ;
 }
 if (root->left != NULL) {
  string nxt = pre + char('0');
  dfs(root->left,nxt);
 }
 if (root->right != NULL) {
  string nxt = pre + char('1');
  dfs(root->right,nxt);
 }
}
int main() {
 scanf("%d",&n);
 for (int i = 0;i < n;i ++) {
  scanf("%d",&freq[i]);
 }
 for (int i = 0;i < n;i ++) {
  Node *tmp = new Node(freq[i]);
  tmp->idx = i;
  que.push(tmp);
 }

 while (que.size() >= 2) {
  Node *left = que.top();
  que.pop();
  Node *right = que.top();
  que.pop();
  Node *root = new Node(left->val + right->val);
  root->left = left;
  root->right = right;
  que.push(root);
 }
 Node *root = que.top();
 que.pop();
 dfs(root,"");

 return 0;
}