# Huffman Code Explained using Heap [Introduction to Algorithms book]

Huffman codes is a widely used technique for compressing data. Huffman codes is a greedy algorithm to build up an optimal way of representing each character as a binary string. Suppose we have a 10,000 character data file that we wish to store. And we observe a character ‘a’ occurs very frequently.
Now, there are many ways to represent a file. We consider a problem of designing a binary character code wherein each character is represented by a unique binary string.

For instance, we need 3 bits to represent five characters [a = 000, b=001, c=010, d=011, e=100]. Now if we use variable length codeword, we could save a lot of space, for instance:

A data file of 200,000 characters contains only the characters (a..e), with above mentioned frequencies. If we use variable-length code instead of fixed-length code, we could save 80,000 bits.

###### Huffman Code Algorithm

Huffman invented a greedy algorithm that constructs an optimal prefix code (variable length code) called Huffman Code.

As we could see from the image above, for the given characters {a, b, c} with frequencies {2, 4, 8} respectively, Huffman Codes (bits 0, 1 on edges) generated are:

a: 00
b: 01
c: 1
###### Pseudocode

This problem could be solved by using a Priority Queue or Heap data structure.

Huffman(C)
1. n = size[C]
2. Q = C
3. for i = 1 to n-1:
4.   new node = z
5.   left[z] = Extract-Min[Q]
6.   right[z] = Extract-Min[Q]
7.   f[z] = f[x] + f[y]
8.   Insert(Q, z)
9. Extract-Min(Q)

Note: Extract-Min(Q) operation removes the top (smallest) member of priority-queue Q and left[z] = Extract-Min[Q] operation removes the smallest element from priority-queue Q and assign it to left[z].

Code Implementation

//
//  main.cpp
//  Huffman Code
//
//  Created by Himanshu on 18/09/21.
//

#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#define MAX 100
using namespace std;

struct node {
int freq;
char letter = NULL;
struct node *left, *right;
};
typedef struct node Node;

bool cmp(const Node *a, const Node *b) {
return (a->freq > b->freq);
}

Node* newNode(int freq, char ch) {
Node *p =  new node();

p->freq = freq;
p->letter = ch;
p->left = NULL;
p->right = NULL;

return p;
}

void printArray(int A[], int n) {
for (int i=0; i<n; i++) {
cout<<A[i];
}
cout<<endl;
}

Node* BuildHuffmanTree (vector<int> freq) {
int n = (int)freq.size();
vector<Node*> minHeap;

for (int i=0; i<n; i++) {
Node *z = newNode(freq[i], (char)(i + 'a'));
minHeap.push_back(z);
push_heap(minHeap.begin(), minHeap.end(), &cmp);
}

while (minHeap.size() > 1) {

//This is a non-alphabet node, hence -1 for ch
Node *z = newNode(0, -1);

Node *x = minHeap.front();
pop_heap(minHeap.begin(), minHeap.end(), &cmp);
minHeap.pop_back();
z->left = x;

Node *y = minHeap.front();
pop_heap(minHeap.begin(), minHeap.end(), &cmp);
minHeap.pop_back();
z->right = y;

z->freq = x->freq + y->freq;

minHeap.push_back(z);
push_heap(minHeap.begin(), minHeap.end(), &cmp);
}

return minHeap.front();
}

void solve (int A[], Node *root, int n) {

if (root->letter != -1) {
cout<<(char)(root->letter)<<": ";
printArray(A, n);
}

if (root->left) {
A[n] = 0;
solve(A, root->left, n+1);
}

if (root->right) {
A[n] = 1;
solve(A, root->right, n+1);
}

}

int main() {
//    char    =    {a,  b,  c, d,  e,  f}
vector<int> freq = {5, 20, 15, 13, 30, 45};
int temp[MAX];

Node *node = BuildHuffmanTree(freq);
solve(temp, node, 0);

return 0;
}



Output

b: 00
e: 01
c: 100
a: 1010
d: 1011
f: 11

Time complexity: O(nlogn) (For calling Heapify operation (which is O(logn)), n times)
Auxiliary Space: O(n) (For creating Heap)

n is the number of alphabet characters