-
Notifications
You must be signed in to change notification settings - Fork 0
/
statichuffman.txt
77 lines (66 loc) · 1.47 KB
/
statichuffman.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<bits/stdc++.h>
using namespace std;
struct Node {
int val;
int freq;
Node *left,*right;
Node(int key,int f){
val = key;
freq = f;
left = NULL;
right = NULL;
}
};
struct compare{
bool operator()(Node* a,Node* b){
return a->freq > b->freq;
}
};
void printcode(Node* N,string output,int sent){
if(N == NULL){
return;
}
if(N->val != sent){
cout<<N->val<<":"<<output<<endl;
}
printcode(N->left,output+'0',sent);
printcode(N->right,output+'1',sent);
}
int main(){
int n,val,freq;
vector<int> gnodes;
cin>>n;
priority_queue<Node*,vector<Node*>,compare> nodes;
for(int i = 0;i < n;i++){
cin>>val>>freq;
gnodes.push_back(val);
nodes.push(new Node(val,freq));
}
Node *n1,*n2;
//cout<<"\nnodes size:"<<nodes.size()<<": nodes .top :"<<nodes.top()->val<<"\n";
while(nodes.size() != 1){
n1 = nodes.top();
nodes.pop();
n2 = nodes.top();
nodes.pop();
int nf = n1->freq + n2->freq;
Node* root = new Node(n+100,nf);
root->left = n1;
root->right = n2;
nodes.push(root);
}
//cout<<"\nnodes size:"<<nodes.size()<<":nodes top : "<<nodes.top()->val<<"\n";
Node* root = nodes.top();
/*
for(int i = 0;i < gnodes.size();i++){
vector<int> codei;
codes(root,gnodes[i],codei);
for(int j = 0;j < codei.size();j++){
cout<<codei[j];
}
cout<<"\n";
}
*/
printcode(root,"",n+100);
return 0;
}