-
Notifications
You must be signed in to change notification settings - Fork 0
/
Huffman Coding
70 lines (57 loc) · 1.5 KB
/
Huffman Coding
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
#include<iostream>
#include <bits/stdc++.h>
using namespace std;
struct MinHeapNode
{
char number;
unsigned freq;
MinHeapNode *left, *right;
MinHeapNode(char number, unsigned freq)
{
left = right = NULL;
this->number = number;
this->freq = freq;
}
};
struct compare {
bool operator()(MinHeapNode* l, MinHeapNode* r)
{
return (l->freq > r->freq);
}
};
void printCodes(struct MinHeapNode* root, string code)
{
if (!root)
return;
if (root->number != '$')
cout << root->number<< ": "<<code<<"\n";
printCodes(root->left,code+"0");
printCodes(root->right,code+"1");
}
void Huffman(char number[], int freq[], int size)
{
struct MinHeapNode *left, *right, *top;
priority_queue<MinHeapNode*, vector<MinHeapNode*>, compare> minHeap;
for (int i = 0; i < size; ++i)
minHeap.push(new MinHeapNode(number[i], freq[i]));
while (minHeap.size() != 1)
{
left = minHeap.top();
minHeap.pop();
right = minHeap.top();
minHeap.pop();
top = new MinHeapNode('$', left->freq + right->freq);
top->left = left;
top->right = right;
minHeap.push(top);
}
printCodes(minHeap.top(), "");
}
int main()
{
char img[] = {'0','1','2','3','4','5','6','7'};
int freq[] = {1,4,2,3,2,12,10,2};
int size = sizeof(img) / sizeof(img[0]);
Huffman(img, freq, size);
return 0;
}