# Canonical Huffman Coding

Canonical Huffman Coding is a technique used for lossless data compression, where characters or symbols are assigned variable-length codes based on their frequency of occurrence. This code demonstrates how to build a Canonical Huffman tree, generate codes for characters, and print both Huffman and Canonical Huffman codes.

## Problem Statement

The goal of the code is to perform Canonical Huffman Coding on a set of characters and their corresponding frequencies. It constructs a Canonical Huffman tree from the given frequencies, generates codes for each character, and then prints both the original Huffman codes and the Canonical Huffman codes.

## Explanation with an Example

Let's consider the input characters: `a`, `b`, `c`, `d`, `e`, `f`, and `g`, with their respective frequencies: `31`, `54`, `15`, `4`, `23`, `52`, and `21`. The code aims to construct a Canonical Huffman tree using these frequencies and then generate both the Huffman codes and Canonical Huffman codes for each character.

## Idea to Solve

To solve this problem, the code uses structures to represent nodes in the tree and the priority queue for building the tree. It constructs a Huffman tree using the given frequencies, generates Huffman codes for each character based on the tree, and then arranges these Huffman codes in canonical form. Finally, it prints both sets of codes.

## Pseudocode

``````TreeNode structure:
Define a structure TreeNode with integer frequency, char data, left, and right attributes

QNode structure:
Define a structure QNode with TreeNode node, next, and prev attributes

PriorityQueue structure:
Define a structure PriorityQueue with QNode front, rear, and size attributes

MapElement structure:
Define a structure MapElement with char key, int value, and MapElement next attributes

MyMap structure:
Define a structure MyMap with MapElement start attribute
Implement newMap, insertByValue methods

newTreeNode method:
Returns a new TreeNode with frequency and character

newPriorityQueue method:
Returns a new PriorityQueue

enQueue method:
Adds a node to the priority queue

isEmpty method:
Returns 1 if the queue is empty, 0 otherwise

peek method:
Returns the front element of the queue

deQueue method:
Removes the front node from the queue

insertByValue method:
Inserts elements into the custom map by value

getCode method:
Recursively generates Huffman codes and inserts them into the custom map

printBinary method:
Converts and prints a number in binary form

printCanonicalCode method:
Prints the Canonical Huffman codes for characters

printTree method:
Prints the Huffman codes for characters

printTreeElement method:
Handles the printing of Huffman codes

buildHuffmanCodes method:
Builds the Huffman tree using frequencies

Main:
Define characters and frequencies
Build Huffman tree
Print Huffman codes
Print Canonical Huffman codes``````

## Algorithm Explanation

1. Define necessary structures for nodes, queues, and maps.
2. Implement methods to create new nodes, new queues, and manage the priority queue.
3. Implement methods to create a custom map, insert elements, and generate Huffman codes.
4. Implement methods to print binary numbers and print Canonical Huffman codes.
5. Implement methods to print Huffman codes and handle printing in the main tree traversal.
6. Build the Huffman tree using the given frequencies.
7. Print Huffman codes.
8. Print Canonical Huffman codes.

## Code Solution

``````/*
C Program
Canonical Huffman Coding
*/
#include <stdio.h>
#include <stdlib.h>

struct TreeNode
{
int first;
char second;
struct TreeNode *left;
struct TreeNode *right;
};
struct QNode
{
struct TreeNode *n;
struct QNode *next;
struct QNode *prev;
};
struct PriorityQueue
{
struct QNode *front;
struct QNode *rear;
int size;
};
struct MapElement
{
char key;
int value;
struct MapElement *next;
};
// Create custom map
struct MyMap
{
struct MapElement *start;
};
struct MyMap *newMap()
{
struct MyMap *map = (struct MyMap *) malloc(sizeof(struct MyMap));
if (map == NULL)
{
printf("\n Memory overflow to Create Map ");
}
else
{
map->start = NULL;
}
return map;
}
// Returns a new tree node
struct TreeNode *newTreeNode(int first, char second)
{
struct TreeNode *node = (struct TreeNode *) malloc(sizeof(struct TreeNode));
if (node == NULL)
{
printf("\n Memory overflow , When creating a new TreeNode");
}
else
{
node->second = second;
node->first = first;
node->left = NULL;
node->right = NULL;
}
return node;
}
// Returns a new queue
struct PriorityQueue *newPriorityQueue()
{
struct PriorityQueue *q = (struct PriorityQueue *) malloc(sizeof(struct PriorityQueue));
if (q == NULL)
{
printf("\n Memory overflow , When creating a new Queue");
}
else
{
q->front = NULL;
q->rear = NULL;
q->size = 0;
}
return q;
}
// Add a node into Priority queue
void enQueue(struct PriorityQueue *q, struct TreeNode *auxiliary)
{
//Create a dynamic node
struct QNode *node = (struct QNode *) malloc(sizeof(struct QNode));
if (node == NULL)
{
printf("\n Memory overflow , When creating a new Queue Node");
}
else
{
// Set node value
node->n = auxiliary;
node->next = NULL;
node->prev = NULL;
if (q->front == NULL)
{
// When adding a first node of queue
q->front = node;
q->rear = node;
}
else if (q->front->n->first >= auxiliary->first)
{
// Add node at beginning position
node->next = q->front;
q->front->prev = node;
q->front = node;
}
else if (q->rear->n->first <= auxiliary->first)
{
// Add node at last position
node->prev = q->rear;
q->rear->next = node;
q->rear = node;
}
else
{
struct QNode *temp = q->front;
// Find the location of inserting priority node
while (temp->n->first < auxiliary->first)
{
temp = temp->next;
}
node->next = temp;
node->prev = temp->prev;
temp->prev = node;
if (node->prev != NULL)
{
node->prev->next = node;
}
}
q->size = q->size + 1;
}
}
int isEmpty(struct PriorityQueue *q)
{
if (q->size == 0)
{
return 1;
}
else
{
return 0;
}
}
// Get a front element of queue
struct TreeNode *peek(struct PriorityQueue *q)
{
if (isEmpty(q) == 1)
{
// When stack is empty
return NULL;
}
else
{
return q->front->n;
}
}
int isSize(struct PriorityQueue *q)
{
return q->size;
}
// Remove a front node of a queue
void deQueue(struct PriorityQueue *q)
{
if (isEmpty(q) == 0)
{
struct QNode *temp = q->front;
q->front->n = NULL;
if (q->front == q->rear)
{
// When queue contains only one node
q->rear = NULL;
q->front = NULL;
}
else
{
q->front = q->front->next;
q->front->prev = NULL;
}
// Change queue size
q->size--;
free(temp);
}
else
{
printf("\n Empty Queue \n");
}
}
// Print elements of queue
void printQdata(struct PriorityQueue *q)
{
struct QNode *node = q->front;
printf("\n Queue Element ");
while (node != NULL)
{
printf("\n %d  %c", node->n->first, node->n->second);
node = node->next;
}
printf("\n");
}
// Construct Huffman Code Tree
struct TreeNode *buildHuffmanCodes(char value[], int frequency[], int n)
{
struct PriorityQueue *q = newPriorityQueue();
struct TreeNode *root = NULL;
struct TreeNode *n1 = NULL;
struct TreeNode *n2 = NULL;
// First add all elements into priority queue
for (int i = 0; i < n; ++i)
{
root = newTreeNode(frequency[i], value[i]);
enQueue(q, root);
}
// printQdata(q);
// Execute loop until the priority queue contains more than 1 node
while (isSize(q) > 1)
{
// Get first smallest node
n1 = peek(q);
//Remove a front element
deQueue(q);
// Get second smallest node
n2 = peek(q);
// Remove a front element
deQueue(q);
// Make new node using two smallest node
root = newTreeNode(n1->first + n2->first, ' ');
// Add new node into priority queue
enQueue(q, root);
// Set left and right child
root->left = n1;
root->right = n2;
}
deQueue(q);
return root;
}
// We creating custom map functionality using linked list
// This function are sorted insert element by value
void insertByValue(struct MyMap *map, char key, int length)
{
struct MapElement *element = (struct MapElement *) malloc(sizeof(struct MapElement));
if (element == NULL)
{
printf("\n Memory overflow to Create map element");
return;
}
element->key = key;
element->value = length;
element->next = NULL;
if (map->start == NULL)
{
// First node of map
map->start = element;
}
else if (length < map->start->value)
{
element->next = map->start;
map->start = element;
}
else
{
struct MapElement *auxiliary = map->start;
// Add new element to its proper position
while (auxiliary != NULL && auxiliary->next != NULL && auxiliary->next->value <= length)
{
auxiliary = auxiliary->next;
}
element->next = auxiliary->next;
auxiliary->next = element;
}
}
// Get the Huffman code
void getCode(struct TreeNode *node, struct MyMap *map, int n)
{
if (node == NULL)
{
return;
}
if (node->left == NULL && node->right == NULL)
{
insertByValue(map, node->second, n);
return;
}
getCode(node->left, map, n + 1);
getCode(node->right, map, n + 1);
}
//Display binary value
void printBinary(int number)
{
if (number == 0)
{
printf("0\n");
return;
}
//flag which is used to print the binary result
int flag = 0;
//compare value from left to right
for (int bits = 31; bits >= 0; bits--)
{
if (((number >> bits) & 1) == 0b1)
{
printf("1");
flag = 1;
}
else if (flag == 1)
{
printf("0");
}
}
printf("\n");
}
// Handles the request of printing canonical huffman code
void printCanonicalCode(struct TreeNode *root)
{
if (root == NULL)
{
return;
}
else
{
struct MyMap *map = newMap();
// Get hamming code
getCode(root, map, 0);
struct MapElement *auxiliary = map->start;
auxiliary = map->start;
int code = -1;
int length = auxiliary->value;
// Iterating elements of map
while (auxiliary != NULL)
{
// Calculate canonical huffman code
code = (code + 1) << (auxiliary->value - length);
printf(" %c : ", auxiliary->key);
// Display binary value
printBinary(code);
length = auxiliary->value;
auxiliary = auxiliary->next;
}
}
}
// Display Huffman code
void printTree(struct TreeNode *node, char result[], int n)
{
if (node == NULL)
{
return;
}
if (node->left == NULL && node->right == NULL)
{
result[n] = '\0';
printf("\n %c %s", node->second, result);
return;
}
result[n] = '0';
printTree(node->left, result, n + 1);
result[n] = '1';
printTree(node->right, result, n + 1);
}
// Handles the request to print Huffman code
void printTreeElement(struct TreeNode *root, int n)
{
if (n < 0 || root == NULL)
{
return;
}
// This is Used to collecting code
char result[n + 1];
printTree(root, result, 0);
}
int main(int argc, char
const *argv[])
{
char value[] = {
'a' , 'b' , 'c' , 'd' , 'e' , 'f' , 'g'
};
// value frequency
int frequency[] = {
31 , 54 , 15 , 4 , 23 , 52 , 21
};
// Get the size
int n = sizeof(frequency) / sizeof(frequency[0]);
struct TreeNode *root = buildHuffmanCodes(value, frequency, n);
printf("\n Huffman code ");
printTreeElement(root, n);
// Finally find canonical huffman code
printf("\n Canonical huffman code \n");
printCanonicalCode(root);
return 0;
}``````

#### Output

`````` Huffman code
d 0000
c 0001
g 001
f 01
b 10
e 110
a 111
Canonical huffman code
f : 0
b : 1
g : 100
e : 101
a : 110
d : 1110
c : 1111``````
``````/*
Java Program
Canonical Huffman Coding
*/
class TreeNode
{
public int first;
public char second;
public TreeNode left;
public TreeNode right;
public TreeNode(int first, char second)
{
this.first = first;
this.second = second;
this.left = null;
this.right = null;
}
}
class QNode
{
public TreeNode n;
public QNode next;
public QNode prev;
public QNode(TreeNode n)
{
this.n = n;
this.prev = null;
this.next = null;
}
}

class MapElement
{
public char key;
public int value;
public MapElement next;
public MapElement(char key,int value)
{
this.key = key;
this.value = value;
this.next = null;
}

};
// Create custom map
class MyMap
{
public MapElement start;
public MyMap()
{
this.start = null;
}
};

class PriorityQueue
{
public QNode front;
public QNode rear;
public int size;
public PriorityQueue()
{
this.front = null;
this.rear = null;
this.size = 0;
}
// Add a node into queue Priority queue
public void enQueue(TreeNode auxiliary)
{
//Create a dynamic node
QNode node = new QNode(auxiliary);
node.n = auxiliary;
if (this.front == null)
{
// When adding a first node of queue
this.front = node;
this.rear = node;
}
else if (this.front.n.first >= auxiliary.first)
{
// Add node at beginning position
node.next = this.front;
this.front.prev = node;
this.front = node;
}
else if (this.rear.n.first <= auxiliary.first)
{
// Add node at last position
node.prev = this.rear;
this.rear.next = node;
this.rear = node;
}
else
{
QNode temp = this.front;
// Find the location of inserting priority node
while (temp.n.first < auxiliary.first)
{
temp = temp.next;
}
node.next = temp;
node.prev = temp.prev;
temp.prev = node;
if (node.prev != null)
{
node.prev.next = node;
}
}
this.size = this.size + 1;
}
public boolean isEmpty()
{
if (this.size == 0)
{
return true;
}
else
{
return false;
}
}
// Get a front element of queue
public TreeNode peek()
{
if (this.isEmpty() == true)
{
System.out.print("\n Empty Queue \n");
// When Queue is empty
return null;
}
else
{
return this.front.n;
}
}
public int isSize()
{
return this.size;
}
// Remove a front node of a queue
public void deQueue()
{
if (this.isEmpty() == false)
{
QNode temp = this.front;
if (this.front == this.rear)
{
// When queue contains only one node
this.rear = null;
this.front = null;
}
else
{
this.front = this.front.next;
this.front.prev = null;
}
// Change queue size
this.size--;
}
}
// Print elements of queue
public void printQdata()
{
QNode node = this.front;
System.out.print("\n Queue Element ");
while (node != null)
{
System.out.print("\n " + node.n.first + " " + node.n.second);
node = node.next;
}
System.out.print("\n");
}
}
public class HuffmanCodes
{
// Display Huffman code
public void printTree(TreeNode node, String result)
{
if (node == null)
{
return;
}
if (node.left == null && node.right == null)
{
System.out.print(" " + node.second + " " + result+"\n");
return;
}
printTree(node.left, result + "0");
printTree(node.right, result + "1");
}
// Construct Huffman Code Tree
public TreeNode buildHuffmanCodes(char[] value, int[] frequency, int n)
{
PriorityQueue q = new PriorityQueue();
TreeNode root = null;
TreeNode n1 = null;
TreeNode n2 = null;
// First add all elements into priority queue
for (int i = 0; i < n; ++i)
{
root = new TreeNode(frequency[i], value[i]);
q.enQueue(root);
}
// printQdata(q);
// Execute loop until the priority queue contains more than 1 node
while (q.isSize() > 1)
{
// Get first smallest node
n1 = q.peek();
//Remove a front element
q.deQueue();
// Get second smallest node
n2 = q.peek();
// Remove a front element
q.deQueue();
// Make new node using two smallest node
root = new TreeNode(n1.first + n2.first, ' ');
// Add new node into priority queue
q.enQueue(root);
// Set left and right child
root.left = n1;
root.right = n2;
}
q.deQueue();
return root;
}
//Get valid value
public char actualValue(int num)
{
if (num >= 0 && num <= 9)
{
return (char)(num + '0');
}
else
{
return (char)(num - 10 + 'A');
}
}
//Display binary value
public void printBinary(int num)
{
if (num == 0)
{
System.out.print("0\n");
return;
}
int n =  num;
//This is used to store result
String result = "";
//Transform decimal to other base
while (num > 0)
{
result = (actualValue(num % 2)) + result;
num /= 2;
}
System.out.print(result+"\n");
}
// We creating custom map functionality using linked list
// This function are sorted insert element by value
public void insertByValue(MyMap map, char key, int length)
{
MapElement element = new MapElement(key,length);
if (element == null)
{
System.out.print("\n Memory overflow to Create map element");
return;
}

if (map.start == null)
{
// First node of map
map.start = element;
}
else if (length < map.start.value)
{
element.next = map.start;
map.start = element;
}
else
{
MapElement auxiliary = map.start;
// Add new element to its proper position
while (auxiliary != null && auxiliary.next != null && auxiliary.next.value <= length)
{
auxiliary = auxiliary.next;
}
element.next = auxiliary.next;
auxiliary.next = element;
}
}
// Get the Huffman code
public void getCode(TreeNode node, MyMap m, int n)
{
if (node == null)
{
return;
}
if (node.left == null && node.right == null)
{
insertByValue(m, node.second, n);
return;
}
getCode(node.left, m, n + 1);
getCode(node.right, m, n + 1);
}
// Handles the request of printing canonical huffman code
public void printCanonicalCode(TreeNode root)
{
if (root == null)
{
return;
}
else
{
MyMap m = new MyMap();
// Get hamming code
getCode(root, m, 0);
MapElement auxiliary = m.start;
auxiliary = m.start;
int code = -1;
int length = auxiliary.value;
// Iterating elements of map
while (auxiliary != null)
{
// Calculate canonical huffman code
code = (code + 1) << (auxiliary.value - length);
System.out.print(" " + auxiliary.key + " : ");
// Display binary value
printBinary(code);
length = auxiliary.value;
auxiliary = auxiliary.next;
}
}
}

public static void main(String[] args)
{
char[] value = {
'a', 'b', 'c', 'd', 'e', 'f','g'
};
int[] frequency = {
31, 54, 15, 4 , 23, 52, 21
};
int n = frequency.length;
TreeNode root = task.buildHuffmanCodes(value, frequency, n);
System.out.println("Huffman Codes");

// Finally find canonical huffman code
System.out.print("\n Canonical huffman code \n");
}
}``````

#### Output

``````Huffman Codes
d 0000
c 0001
g 001
f 01
b 10
e 110
a 111

Canonical huffman code
f : 0
b : 1
g : 100
e : 101
a : 110
d : 1110
c : 1111``````
``````// Include header file
#include <iostream>

#include <string.h>

using namespace std;
/*
C++ Program
Canonical Huffman Coding
*/
class TreeNode
{
public: int first;
char second;
TreeNode *left;
TreeNode *right;
TreeNode(int first, char second)
{
this->first = first;
this->second = second;
this->left = NULL;
this->right = NULL;
}
};
class QNode
{
public: TreeNode *n;
QNode *next;
QNode *prev;
QNode(TreeNode *n)
{
this->n = n;
this->prev = NULL;
this->next = NULL;
}
};
class MapElement
{
public: char key;
int value;
MapElement *next;
MapElement(char key, int value)
{
this->key = key;
this->value = value;
this->next = NULL;
}
};;
// Create custom map
class MyMap
{
public: MapElement *start;
MyMap()
{
this->start = NULL;
}
};;
class PriorityQueue
{
public: QNode *front;
QNode *rear;
int size;
PriorityQueue()
{
this->front = NULL;
this->rear = NULL;
this->size = 0;
}
// Add a node into queue Priority queue
void enQueue(TreeNode *auxiliary)
{
//Create a dynamic node
QNode *node = new QNode(auxiliary);
node->n = auxiliary;
if (this->front == NULL)
{
// When adding a first node of queue
this->front = node;
this->rear = node;
}
else if (this->front->n->first >= auxiliary->first)
{
// Add node at beginning position
node->next = this->front;
this->front->prev = node;
this->front = node;
}
else if (this->rear->n->first <= auxiliary->first)
{
// Add node at last position
node->prev = this->rear;
this->rear->next = node;
this->rear = node;
}
else
{
QNode *temp = this->front;
// Find the location of inserting priority node
while (temp->n->first < auxiliary->first)
{
temp = temp->next;
}
node->next = temp;
node->prev = temp->prev;
temp->prev = node;
if (node->prev != NULL)
{
node->prev->next = node;
}
}
this->size = this->size + 1;
}
bool isEmpty()
{
if (this->size == 0)
{
return true;
}
else
{
return false;
}
}
// Get a front element of queue
TreeNode *peek()
{
if (this->isEmpty() == true)
{
// When Queue is empty
cout << "\n Empty Queue \n";
return NULL;
}
else
{
return this->front->n;
}
}
int isSize()
{
return this->size;
}
// Remove a front node of a queue
void deQueue()
{
if (this->isEmpty() == false)
{
QNode *temp = this->front;
if (this->front == this->rear)
{
// When queue contains only one node
this->rear = NULL;
this->front = NULL;
}
else
{
this->front = this->front->next;
this->front->prev = NULL;
}
// Change queue size
this->size--;
}
}
// Print elements of queue
void printQdata()
{
QNode *node = this->front;
cout << "\n Queue Element ";
while (node != NULL)
{
cout << "\n " << node->n->first << " " << node->n->second;
node = node->next;
}
cout << "\n";
}
};
class HuffmanCodes
{
public:
// Display Huffman code
void printTree(TreeNode *node, string result)
{
if (node == NULL)
{
return;
}
if (node->left == NULL && node->right == NULL)
{
cout << " " << node->second << " " << result << "\n";
return;
}
this->printTree(node->left, result + "0");
this->printTree(node->right, result + "1");
}
// Construct Huffman Code Tree
TreeNode *buildHuffmanCodes(char value[], int frequency[], int n)
{
PriorityQueue q = PriorityQueue();
TreeNode *root = NULL;
TreeNode *n1 = NULL;
TreeNode *n2 = NULL;
// First add all elements into priority queue
for (int i = 0; i < n; ++i)
{
root = new TreeNode(frequency[i], value[i]);
q.enQueue(root);
}
// printQdata(q);
// Execute loop until the priority queue contains more than 1 node
while (q.isSize() > 1)
{
// Get first smallest node
n1 = q.peek();
//Remove a front element
q.deQueue();
// Get second smallest node
n2 = q.peek();
// Remove a front element
q.deQueue();
// Make new node using two smallest node
root = new TreeNode(n1->first + n2->first, ' ');
// Add new node into priority queue
q.enQueue(root);
// Set left and right child
root->left = n1;
root->right = n2;
}
q.deQueue();
return root;
}
//Get valid value
char actualValue(int num)
{
if (num >= 0 && num <= 9)
{
return (char)(num + '0');
}
else
{
return (char)(num - 10 + 'A');
}
}
//Display binary value
void printBinary(int num)
{
if (num == 0)
{
cout << "0\n";
return;
}
int n = num;
//This is used to store result
string result = "";
//Transform decimal to other base
while (num > 0)
{
result = (this->actualValue(num % 2)) + result;
num /= 2;
}
cout << result << "\n";
}
// We creating custom map functionality using linked list
// This function are sorted insert element by value
void insertByValue(MyMap *map, char key, int length)
{
MapElement *element = new MapElement(key, length);
if (element == NULL)
{
cout << "\n Memory overflow to Create map element";
return;
}
if (map->start == NULL)
{
// First node of map
map->start = element;
}
else if (length < map->start->value)
{
element->next = map->start;
map->start = element;
}
else
{
MapElement *auxiliary = map->start;
// Add new element to its proper position
while (auxiliary != NULL && auxiliary->next != NULL && auxiliary->next->value <= length)
{
auxiliary = auxiliary->next;
}
element->next = auxiliary->next;
auxiliary->next = element;
}
}
// Get the Huffman code
void getCode(TreeNode *node, MyMap *m, int n)
{
if (node == NULL)
{
return;
}
if (node->left == NULL && node->right == NULL)
{
this->insertByValue(m, node->second, n);
return;
}
this->getCode(node->left, m, n + 1);
this->getCode(node->right, m, n + 1);
}
// Handles the request of printing canonical huffman code
void printCanonicalCode(TreeNode *root)
{
if (root == NULL)
{
return;
}
else
{
MyMap *m = new MyMap();
// Get hamming code
this->getCode(root, m, 0);
MapElement *auxiliary = m->start;
auxiliary = m->start;
int code = -1;
int length = auxiliary->value;
// Iterating elements of map
while (auxiliary != NULL)
{
// Calculate canonical huffman code
code = (code + 1) << (auxiliary->value - length);
cout << " " << auxiliary->key << " : ";
// Display binary value
this->printBinary(code);
length = auxiliary->value;
auxiliary = auxiliary->next;
}
}
}
};
int main()
{
char value[] = {
'a' , 'b' , 'c' , 'd' , 'e' , 'f' , 'g'
};
int frequency[] = {
31 , 54 , 15 , 4 , 23 , 52 , 21
};
int n = sizeof(frequency) / sizeof(frequency[0]);
TreeNode *root = task.buildHuffmanCodes(value, frequency, n);
cout << "Huffman Codes";
// Finally find canonical huffman code
cout << "\n Canonical huffman code \n";
return 0;
}``````

#### Output

``````Huffman Codes d 0000
c 0001
g 001
f 01
b 10
e 110
a 111

Canonical huffman code
f : 0
b : 1
g : 100
e : 101
a : 110
d : 1110
c : 1111``````
``````// Include namespace system
using System;
/*
C# Program
Canonical Huffman Coding
*/
public class TreeNode
{
public int first;
public char second;
public TreeNode left;
public TreeNode right;
public TreeNode(int first, char second)
{
this.first = first;
this.second = second;
this.left = null;
this.right = null;
}
}
public class QNode
{
public TreeNode n;
public QNode next;
public QNode prev;
public QNode(TreeNode n)
{
this.n = n;
this.prev = null;
this.next = null;
}
}
public class MapElement
{
public char key;
public int value;
public MapElement next;
public MapElement(char key, int value)
{
this.key = key;
this.value = value;
this.next = null;
}
};
// Create custom map
public class MyMap
{
public MapElement start;
public MyMap()
{
this.start = null;
}
};
public class PriorityQueue
{
public QNode front;
public QNode rear;
public int size;
public PriorityQueue()
{
this.front = null;
this.rear = null;
this.size = 0;
}
// Add a node into queue Priority queue
public void enQueue(TreeNode auxiliary)
{
//Create a dynamic node
QNode node = new QNode(auxiliary);
node.n = auxiliary;
if (this.front == null)
{
// When adding a first node of queue
this.front = node;
this.rear = node;
}
else if (this.front.n.first >= auxiliary.first)
{
// Add node at beginning position
node.next = this.front;
this.front.prev = node;
this.front = node;
}
else if (this.rear.n.first <= auxiliary.first)
{
// Add node at last position
node.prev = this.rear;
this.rear.next = node;
this.rear = node;
}
else
{
QNode temp = this.front;
// Find the location of inserting priority node
while (temp.n.first < auxiliary.first)
{
temp = temp.next;
}
node.next = temp;
node.prev = temp.prev;
temp.prev = node;
if (node.prev != null)
{
node.prev.next = node;
}
}
this.size = this.size + 1;
}
public Boolean isEmpty()
{
if (this.size == 0)
{
return true;
}
else
{
return false;
}
}
// Get a front element of queue
public TreeNode peek()
{
if (this.isEmpty() == true)
{
// When Queue is empty
Console.Write("\n Empty Queue \n");
return null;
}
else
{
return this.front.n;
}
}
public int isSize()
{
return this.size;
}
// Remove a front node of a queue
public void deQueue()
{
if (this.isEmpty() == false)
{
QNode temp = this.front;
temp.n = null;
if (this.front == this.rear)
{
// When queue contains only one node
this.rear = null;
this.front = null;
}
else
{
this.front = this.front.next;
this.front.prev = null;
}
// Change queue size
this.size--;
}
}
// Print elements of queue
public void printQdata()
{
QNode node = this.front;
Console.Write("\n Queue Element ");
while (node != null)
{
Console.Write("\n " + node.n.first + " " + node.n.second);
node = node.next;
}
Console.Write("\n");
}
}
public class HuffmanCodes
{
// Display Huffman code
public void printTree(TreeNode node, String result)
{
if (node == null)
{
return;
}
if (node.left == null && node.right == null)
{
Console.Write(" " + node.second + " " + result + "\n");
return;
}
printTree(node.left, result + "0");
printTree(node.right, result + "1");
}
// Construct Huffman Code Tree
public TreeNode buildHuffmanCodes(char[] value, int[] frequency, int n)
{
PriorityQueue q = new PriorityQueue();
TreeNode root = null;
TreeNode n1 = null;
TreeNode n2 = null;
// First add all elements into priority queue
for (int i = 0; i < n; ++i)
{
root = new TreeNode(frequency[i], value[i]);
q.enQueue(root);
}
// printQdata(q);
// Execute loop until the priority queue contains more than 1 node
while (q.isSize() > 1)
{
// Get first smallest node
n1 = q.peek();
//Remove a front element
q.deQueue();
// Get second smallest node
n2 = q.peek();
// Remove a front element
q.deQueue();
// Make new node using two smallest node
root = new TreeNode(n1.first + n2.first, ' ');
// Add new node into priority queue
q.enQueue(root);
// Set left and right child
root.left = n1;
root.right = n2;
}
q.deQueue();
return root;
}
//Get valid value
public char actualValue(int num)
{
if (num >= 0 && num <= 9)
{
return (char)(num + '0');
}
else
{
return (char)(num - 10 + 'A');
}
}
//Display binary value
public void printBinary(int num)
{
if (num == 0)
{
Console.Write("0\n");
return;
}
int n = num;
//This is used to store result
String result = "";
//Transform decimal to other base
while (n > 0)
{
result = (actualValue(n % 2)) + result;
n /= 2;
}
Console.Write(result + "\n");
}
// We creating custom map functionality using linked list
// This function are sorted insert element by value
public void insertByValue(MyMap map, char key, int length)
{
MapElement element = new MapElement(key, length);
if (element == null)
{
Console.Write("\n Memory overflow to Create map element");
return;
}
if (map.start == null)
{
// First node of map
map.start = element;
}
else if (length < map.start.value)
{
element.next = map.start;
map.start = element;
}
else
{
MapElement auxiliary = map.start;
// Add new element to its proper position
while (auxiliary != null && auxiliary.next != null
&& auxiliary.next.value <= length)
{
auxiliary = auxiliary.next;
}
element.next = auxiliary.next;
auxiliary.next = element;
}
}
// Get the Huffman code
public void getCode(TreeNode node, MyMap m, int n)
{
if (node == null)
{
return;
}
if (node.left == null && node.right == null)
{
insertByValue(m, node.second, n);
return;
}
getCode(node.left, m, n + 1);
getCode(node.right, m, n + 1);
}
// Handles the request of printing canonical huffman code
public void printCanonicalCode(TreeNode root)
{
if (root == null)
{
return;
}
else
{
MyMap m = new MyMap();
// Get hamming code
getCode(root, m, 0);
MapElement auxiliary = m.start;
auxiliary = m.start;
int code = -1;
int length = auxiliary.value;
// Iterating elements of map
while (auxiliary != null)
{
// Calculate canonical huffman code
code = (code + 1) << (auxiliary.value - length);
Console.Write(" " + auxiliary.key + " : ");
// Display binary value
printBinary(code);
length = auxiliary.value;
auxiliary = auxiliary.next;
}
}
}
public static void Main(String[] args)
{
char[] value = {
'a' , 'b' , 'c' , 'd' , 'e' , 'f' , 'g'
};
int[] frequency = {
31 , 54 , 15 , 4 , 23 , 52 , 21
};
int n = frequency.Length;
TreeNode root = task.buildHuffmanCodes(value, frequency, n);
Console.WriteLine("Huffman Codes");
// Finally find canonical huffman code
Console.Write("\n Canonical huffman code \n");
}
}``````

#### Output

``````Huffman Codes
d 0000
c 0001
g 001
f 01
b 10
e 110
a 111

Canonical huffman code
f : 0
b : 1
g : 100
e : 101
a : 110
d : 1110
c : 1111``````
``````<?php
/*
Php Program
Canonical Huffman Coding
*/
class TreeNode
{
public \$first;
public \$second;
public \$left;
public \$right;

function __construct(\$first, \$second)
{
\$this->first = \$first;
\$this->second = \$second;
\$this->left = null;
\$this->right = null;
}
}
class QNode
{
public \$n;
public \$next;
public \$prev;

function __construct(\$n)
{
\$this->n = \$n;
\$this->prev = null;
\$this->next = null;
}
}
class MapElement
{
public \$key;
public \$value;
public \$next;

function __construct(\$key, \$value)
{
\$this->key = \$key;
\$this->value = \$value;
\$this->next = null;
}
};
// Create custom map
class MyMap
{
public \$start;

function __construct()
{
\$this->start = null;
}
};
class PriorityQueue
{
public \$front;
public \$rear;
public \$size;

function __construct()
{
\$this->front = null;
\$this->rear = null;
\$this->size = 0;
}
// Add a node into queue Priority queue
public	function enQueue(\$auxiliary)
{
//Create a dynamic node
\$node = new QNode(\$auxiliary);
\$node->n = \$auxiliary;
if (\$this->front == null)
{
// When adding a first node of queue
\$this->front = \$node;
\$this->rear = \$node;
}
else if (\$this->front->n->first >= \$auxiliary->first)
{
// Add node at beginning position
\$node->next = \$this->front;
\$this->front->prev = \$node;
\$this->front = \$node;
}
else if (\$this->rear->n->first <= \$auxiliary->first)
{
// Add node at last position
\$node->prev = \$this->rear;
\$this->rear->next = \$node;
\$this->rear = \$node;
}
else
{
\$temp = \$this->front;
// Find the location of inserting priority node
while (\$temp->n->first < \$auxiliary->first)
{
\$temp = \$temp->next;
}
\$node->next = \$temp;
\$node->prev = \$temp->prev;
\$temp->prev = \$node;
if (\$node->prev != null)
{
\$node->prev->next = \$node;
}
}
\$this->size = \$this->size + 1;
}
public	function isEmpty()
{
if (\$this->size == 0)
{
return true;
}
else
{
return false;
}
}
// Get a front element of queue
public	function peek()
{
if (\$this->isEmpty() == true)
{
// When Queue is empty
echo "\n Empty Queue \n";
return null;
}
else
{
return \$this->front->n;
}
}
public	function isSize()
{
return \$this->size;
}
// Remove a front node of a queue
public	function deQueue()
{
if (\$this->isEmpty() == false)
{
\$temp = \$this->front;
\$temp->n = null;
if (\$this->front == \$this->rear)
{
// When queue contains only one node
\$this->rear = null;
\$this->front = null;
}
else
{
\$this->front = \$this->front->next;
\$this->front->prev = null;
}
// Change queue size
\$this->size--;
}
}
// Print elements of queue
public	function printQdata()
{
\$node = \$this->front;
echo "\n Queue Element ";
while (\$node != null)
{
echo "\n ". \$node->n->first ." ". \$node->n->second;
\$node = \$node->next;
}
echo "\n";
}
}
class HuffmanCodes
{
// Display Huffman code
public	function printTree(\$node, \$result)
{
if (\$node == null)
{
return;
}
if (\$node->left == null && \$node->right == null)
{
echo " ". \$node->second ." ". \$result ."\n";
return;
}
\$this->printTree(\$node->left, \$result ."0");
\$this->printTree(\$node->right, \$result ."1");
}
// Construct Huffman Code Tree
public	function buildHuffmanCodes( & \$value, & \$frequency, \$n)
{
\$q = new PriorityQueue();
\$root = null;
\$n1 = null;
\$n2 = null;
// First add all elements into priority queue
for (\$i = 0; \$i < \$n; ++\$i)
{
\$root = new TreeNode(\$frequency[\$i], \$value[\$i]);
\$q->enQueue(\$root);
}
// printQdata(q);
// Execute loop until the priority queue contains more than 1 node
while (\$q->isSize() > 1)
{
// Get first smallest node
\$n1 = \$q->peek();
//Remove a front element
\$q->deQueue();
// Get second smallest node
\$n2 = \$q->peek();
// Remove a front element
\$q->deQueue();
// Make new node using two smallest node
\$root = new TreeNode(\$n1->first + \$n2->first, ' ');
// Add new node into priority queue
\$q->enQueue(\$root);
// Set left and right child
\$root->left = \$n1;
\$root->right = \$n2;
}
\$q->deQueue();
return \$root;
}
//Get valid value
public	function actualValue(\$num)
{
if (\$num >= 0 && \$num <= 9)
{
return (string)(\$num + '0');
}
else
{
return (string)(\$num - 10 + 'A');
}
}
//Display binary value
public	function printBinary(\$num)
{
if (\$num == 0)
{
echo "0\n";
return;
}
\$n = \$num;
//This is used to store result
\$result = "";
//Transform decimal to other base
while (\$n > 0)
{
\$result = (\$this->actualValue(\$n % 2)) . \$result;
\$n = intval(\$n / 2);
}
echo \$result ."\n";
}
// We creating custom map functionality using linked list
// This function are sorted insert element by value
public	function insertByValue(\$map, \$key, \$length)
{
\$element = new MapElement(\$key, \$length);
if (\$element == null)
{
echo "\n Memory overflow to Create map element";
return;
}
if (\$map->start == null)
{
// First node of map
\$map->start = \$element;
}
else if (\$length < \$map->start->value)
{
\$element->next = \$map->start;
\$map->start = \$element;
}
else
{
\$auxiliary = \$map->start;
// Add new element to its proper position
while (\$auxiliary != null && \$auxiliary->next != null && \$auxiliary->next->value <= \$length)
{
\$auxiliary = \$auxiliary->next;
}
\$element->next = \$auxiliary->next;
\$auxiliary->next = \$element;
}
}
// Get the Huffman code
public	function getCode(\$node, \$m, \$n)
{
if (\$node == null)
{
return;
}
if (\$node->left == null && \$node->right == null)
{
\$this->insertByValue(\$m, \$node->second, \$n);
return;
}
\$this->getCode(\$node->left, \$m, \$n + 1);
\$this->getCode(\$node->right, \$m, \$n + 1);
}
// Handles the request of printing canonical huffman code
public	function printCanonicalCode(\$root)
{
if (\$root == null)
{
return;
}
else
{
\$m = new MyMap();
// Get hamming code
\$this->getCode(\$root, \$m, 0);
\$auxiliary = \$m->start;
\$auxiliary = \$m->start;
\$code = -1;
\$length = \$auxiliary->value;
// Iterating elements of map
while (\$auxiliary != null)
{
// Calculate canonical huffman code
\$code = (\$code + 1) << (\$auxiliary->value - \$length);
echo " ". \$auxiliary->key ." : ";
// Display binary value
\$this->printBinary(\$code);
\$length = \$auxiliary->value;
\$auxiliary = \$auxiliary->next;
}
}
}
}

function main()
{
\$value = array('a', 'b', 'c', 'd', 'e', 'f', 'g');
\$frequency = array(31, 54, 15, 4, 23, 52, 21);
\$n = count(\$frequency);
echo "Huffman Codes";
// Finally find canonical huffman code
echo "\n Canonical huffman code \n";
}
main();``````

#### Output

``````Huffman Codes d 0000
c 0001
g 001
f 01
b 10
e 110
a 111

Canonical huffman code
f : 0
b : 1
g : 100
e : 101
a : 110
d : 1110
c : 1111``````
``````/*
Node Js Program
Canonical Huffman Coding
*/
class TreeNode
{
constructor(first, second)
{
this.first = first;
this.second = second;
this.left = null;
this.right = null;
}
}
class QNode
{
constructor(n)
{
this.n = n;
this.prev = null;
this.next = null;
}
}
class MapElement
{
constructor(key, value)
{
this.key = key;
this.value = value;
this.next = null;
}
};
// Create custom map
class MyMap
{
constructor()
{
this.start = null;
}
};
class PriorityQueue
{
constructor()
{
this.front = null;
this.rear = null;
this.size = 0;
}
// Add a node into queue Priority queue
enQueue(auxiliary)
{
//Create a dynamic node
var node = new QNode(auxiliary);
node.n = auxiliary;
if (this.front == null)
{
// When adding a first node of queue
this.front = node;
this.rear = node;
}
else if (this.front.n.first >= auxiliary.first)
{
// Add node at beginning position
node.next = this.front;
this.front.prev = node;
this.front = node;
}
else if (this.rear.n.first <= auxiliary.first)
{
// Add node at last position
node.prev = this.rear;
this.rear.next = node;
this.rear = node;
}
else
{
var temp = this.front;
// Find the location of inserting priority node
while (temp.n.first < auxiliary.first)
{
temp = temp.next;
}
node.next = temp;
node.prev = temp.prev;
temp.prev = node;
if (node.prev != null)
{
node.prev.next = node;
}
}
this.size = this.size + 1;
}
isEmpty()
{
if (this.size == 0)
{
return true;
}
else
{
return false;
}
}
// Get a front element of queue
peek()
{
if (this.isEmpty() == true)
{
// When Queue is empty
process.stdout.write("\n Empty Queue \n");
return null;
}
else
{
return this.front.n;
}
}
isSize()
{
return this.size;
}
// Remove a front node of a queue
deQueue()
{
if (this.isEmpty() == false)
{
var temp = this.front;
temp.n = null;
if (this.front == this.rear)
{
// When queue contains only one node
this.rear = null;
this.front = null;
}
else
{
this.front = this.front.next;
this.front.prev = null;
}
// Change queue size
this.size--;
}
}
// Print elements of queue
printQdata()
{
var node = this.front;
process.stdout.write("\n Queue Element ");
while (node != null)
{
process.stdout.write("\n " + node.n.first + " " + node.n.second);
node = node.next;
}
process.stdout.write("\n");
}
}
class HuffmanCodes
{
// Display Huffman code
printTree(node, result)
{
if (node == null)
{
return;
}
if (node.left == null && node.right == null)
{
process.stdout.write(" " + node.second + " " + result + "\n");
return;
}
this.printTree(node.left, result + "0");
this.printTree(node.right, result + "1");
}
// Construct Huffman Code Tree
buildHuffmanCodes(value, frequency, n)
{
var q = new PriorityQueue();
var root = null;
var n1 = null;
var n2 = null;
// First add all elements into priority queue
for (var i = 0; i < n; ++i)
{
root = new TreeNode(frequency[i], value[i]);
q.enQueue(root);
}
// printQdata(q);
// Execute loop until the priority queue contains more than 1 node
while (q.isSize() > 1)
{
// Get first smallest node
n1 = q.peek();
//Remove a front element
q.deQueue();
// Get second smallest node
n2 = q.peek();
// Remove a front element
q.deQueue();
// Make new node using two smallest node
root = new TreeNode(n1.first + n2.first, ' ');
// Add new node into priority queue
q.enQueue(root);
// Set left and right child
root.left = n1;
root.right = n2;
}
q.deQueue();
return root;
}
//Get valid value
actualValue(num)
{
if (num >= 0 && num <= 9)
{
return (String.fromCharCode(num + '0'.charCodeAt(0)));
}
else
{
return (String.fromCharCode(num - 10 + 'A'.charCodeAt(0)));
}
}
//Display binary value
printBinary(num)
{
if (num == 0)
{
process.stdout.write("0\n");
return;
}
var n = num;
//This is used to store result
var result = "";
//Transform decimal to other base
while (n > 0)
{
result = (this.actualValue(n % 2)) + result;
n = parseInt(n / 2);
}
process.stdout.write(result+"\n");
}
// We creating custom map functionality using linked list
// This function are sorted insert element by value
insertByValue(map, key, length)
{
var element = new MapElement(key, length);
if (element == null)
{
process.stdout.write("\n Memory overflow to Create map element");
return;
}
if (map.start == null)
{
// First node of map
map.start = element;
}
else if (length < map.start.value)
{
element.next = map.start;
map.start = element;
}
else
{
var auxiliary = map.start;
// Add new element to its proper position
while (auxiliary != null && auxiliary.next != null
&& auxiliary.next.value <= length)
{
auxiliary = auxiliary.next;
}
element.next = auxiliary.next;
auxiliary.next = element;
}
}
// Get the Huffman code
getCode(node, m, n)
{
if (node == null)
{
return;
}
if (node.left == null && node.right == null)
{
this.insertByValue(m, node.second, n);
return;
}
this.getCode(node.left, m, n + 1);
this.getCode(node.right, m, n + 1);
}
// Handles the request of printing canonical huffman code
printCanonicalCode(root)
{
if (root == null)
{
return;
}
else
{
var m = new MyMap();
// Get hamming code
this.getCode(root, m, 0);
var auxiliary = m.start;
auxiliary = m.start;
var code = -1;
var length = auxiliary.value;
// Iterating elements of map
while (auxiliary != null)
{
// Calculate canonical huffman code
code = (code + 1) << (auxiliary.value - length);
process.stdout.write(" " + auxiliary.key + " : " );
// Display binary value
this.printBinary(code);
length = auxiliary.value;
auxiliary = auxiliary.next;
}
}
}
}

function main()
{
var value = ['a', 'b', 'c', 'd', 'e', 'f', 'g'];
var frequency = [31, 54, 15, 4, 23, 52, 21];
var n = frequency.length;
var root = task.buildHuffmanCodes(value, frequency, n);
process.stdout.write("Huffman Codes");
// Finally find canonical huffman code
process.stdout.write("\n Canonical huffman code \n");
}
main();``````

#### Output

``````Huffman Codes d 0000
c 0001
g 001
f 01
b 10
e 110
a 111

Canonical huffman code
f : 0
b : 1
g : 100
e : 101
a : 110
d : 1110
c : 1111``````
``````#
#     Python 3 Program
#     Canonical Huffman Coding

class TreeNode :

def __init__(self, first, second) :
self.first = first
self.second = second
self.left = None
self.right = None

class QNode :

def __init__(self, n) :
self.n = n
self.prev = None
self.next = None

class MapElement :

def __init__(self, key, value) :
self.key = key
self.value = value
self.next = None

#  Create custom map
class MyMap :

def __init__(self) :
self.start = None

class PriorityQueue :

def __init__(self) :
self.front = None
self.rear = None
self.size = 0

#  Add a node into queue Priority queue
def enQueue(self, auxiliary) :
# Create a dynamic node
node = QNode(auxiliary)
node.n = auxiliary
if (self.front == None) :
#  When adding a first node of queue
self.front = node
self.rear = node

elif(self.front.n.first >= auxiliary.first) :
#  Add node at beginning position
node.next = self.front
self.front.prev = node
self.front = node

elif(self.rear.n.first <= auxiliary.first) :
#  Add node at last position
node.prev = self.rear
self.rear.next = node
self.rear = node
else :
temp = self.front
#  Find the location of inserting priority node
while (temp.n.first < auxiliary.first) :
temp = temp.next

node.next = temp
node.prev = temp.prev
temp.prev = node
if (node.prev != None) :
node.prev.next = node

self.size = self.size + 1

def isEmpty(self) :
if (self.size == 0) :
return True
else :
return False

#  Get a front element of queue
def peek(self) :
if (self.isEmpty() == True) :
#  When Queue is empty
print("\n Empty Queue ")
return None
else :
return self.front.n

def isSize(self) :
return self.size

#  Remove a front node of a queue
def deQueue(self) :
if (self.isEmpty() == False) :
temp = self.front
temp.n = None
if (self.front == self.rear) :
#  When queue contains only one node
self.rear = None
self.front = None
else :
self.front = self.front.next
self.front.prev = None

#  Change queue size
self.size -= 1

#  Print elements of queue
def printQdata(self) :
node = self.front
print("\n Queue Element ", end = "")
while (node != None) :
print("\n ", node.n.first ," ", node.n.second, end = "")
node = node.next

print(end = "\n")

class HuffmanCodes :
#  Display Huffman code
def printTree(self, node, result) :
if (node == None) :
return

if (node.left == None and node.right == None) :
print(" ", node.second ," ", result )
return

self.printTree(node.left, result+"0")
self.printTree(node.right, result+"1")

#  Construct Huffman Code Tree
def buildHuffmanCodes(self, value, frequency, n) :
q = PriorityQueue()
root = None
n1 = None
n2 = None
#  First add all elements into priority queue
i = 0
while (i < n) :
root = TreeNode(frequency[i], value[i])
q.enQueue(root)
i += 1

#  printQdata(q)
#  Execute loop until the priority queue contains more than 1 node
while (q.isSize() > 1) :
#  Get first smallest node
n1 = q.peek()
# Remove a front element
q.deQueue()
#  Get second smallest node
n2 = q.peek()
#  Remove a front element
q.deQueue()
#  Make new node using two smallest node
root = TreeNode(n1.first + n2.first, ' ')
#  Add new node into priority queue
q.enQueue(root)
#  Set left and right child
root.left = n1
root.right = n2

q.deQueue()
return root

# Get valid value
def actualValue(self, num) :
if (num >= 0 and num <= 9) :
return (chr(num + ord('0')))
else :
return (chr(num - 10 + ord('A')))

# Display binary value
def printBinary(self, num) :
if (num == 0) :
print("0")
return

n = num
# This is used to store result
result = ""
# Transform decimal to other base
while (n > 0) :
result = (self.actualValue(n % 2)) + result
n = int(n / 2)

print(result )

#  We creating custom map functionality using linked list
#  This function are sorted insert element by value
def insertByValue(self, map, key, length) :
element = MapElement(key, length)
if (element == None) :
print("\n Memory overflow to Create map element", end = "")
return

if (map.start == None) :
#  First node of map
map.start = element

elif(length < map.start.value) :
element.next = map.start
map.start = element
else :
auxiliary = map.start
#  Add new element to its proper position
while (auxiliary != None and auxiliary.next != None and auxiliary.next.value <= length) :
auxiliary = auxiliary.next

element.next = auxiliary.next
auxiliary.next = element

#  Get the Huffman code
def getCode(self, node, m, n) :
if (node == None) :
return

if (node.left == None and node.right == None) :
self.insertByValue(m, node.second, n)
return

self.getCode(node.left, m, n + 1)
self.getCode(node.right, m, n + 1)

#  Handles the request of printing canonical huffman code
def printCanonicalCode(self, root) :
if (root == None) :
return
else :
m = MyMap()
#  Get hamming code
self.getCode(root, m, 0)
auxiliary = m.start
auxiliary = m.start
code = -1
length = auxiliary.value
#  Iterating elements of map
while (auxiliary != None) :
#  Calculate canonical huffman code
code = (code + 1) << (auxiliary.value - length)
print(" ", auxiliary.key ," : ", end = "")
#  Display binary value
self.printBinary(code)
length = auxiliary.value
auxiliary = auxiliary.next

def main() :
value = ['a', 'b', 'c', 'd', 'e', 'f', 'g']
frequency = [31, 54, 15, 4, 23, 52, 21]
n = len(frequency)
print("Huffman Codes", end = "\n")
#  Finally find canonical huffman code
print("\n Canonical huffman code ")

if __name__ == "__main__": main()``````

#### Output

``````Huffman Codes
d   0000
c   0001
g   001
f   01
b   10
e   110
a   111

Canonical huffman code
f  : 0
b  : 1
g  : 100
e  : 101
a  : 110
d  : 1110
c  : 1111``````
``````#   Ruby Program
#   Canonical Huffman Coding

class TreeNode
# Define the accessor and reader of class TreeNode
attr_accessor :first, :second, :left, :right

def initialize(first, second)
self.first = first
self.second = second
self.left = nil
self.right = nil
end

end

class QNode
# Define the accessor and reader of class QNode
attr_accessor :n, :next, :prev

def initialize(n)
self.n = n
self.prev = nil
self.next = nil
end

end

class MapElement
# Define the accessor and reader of class MapElement
attr_accessor :key, :value, :next

def initialize(key, value)
self.key = key
self.value = value
self.next = nil
end

end

#  Create custom map
class MyMap
# Define the accessor and reader of class MyMap
attr_accessor :start

def initialize()
self.start = nil
end

end

class PriorityQueue
# Define the accessor and reader of class PriorityQueue
attr_accessor :front, :rear, :size

def initialize()
self.front = nil
self.rear = nil
self.size = 0
end

#  Add a node into queue Priority queue
def enQueue(auxiliary)
# Create a dynamic node
node = QNode.new(auxiliary)
node.n = auxiliary
if (self.front == nil)
#  When adding a first node of queue
self.front = node
self.rear = node
elsif(self.front.n.first >= auxiliary.first)
#  Add node at beginning position
node.next = self.front
self.front.prev = node
self.front = node
elsif(self.rear.n.first <= auxiliary.first)
#  Add node at last position
node.prev = self.rear
self.rear.next = node
self.rear = node
else
temp = self.front
#  Find the location of inserting priority node
while (temp.n.first < auxiliary.first)
temp = temp.next
end

node.next = temp
node.prev = temp.prev
temp.prev = node
if (node.prev != nil)
node.prev.next = node
end

end

self.size = self.size + 1
end

def isEmpty()
if (self.size == 0)
return true
else
return false
end

end

#  Get a front element of queue
def peek()
if (self.isEmpty() == true)
#  When Queue is empty
print("\n Empty Queue \n")
return nil
else
return self.front.n
end

end

def isSize()
return self.size
end

#  Remove a front node of a queue
def deQueue()
if (self.isEmpty() == false)
temp = self.front
temp.n = nil
if (self.front == self.rear)
#  When queue contains only one node
self.rear = nil
self.front = nil
else
self.front = self.front.next
self.front.prev = nil
end

#  Change queue size
self.size -= 1
end

end

#  Print elements of queue
def printQdata()
node = self.front
print("\n Queue Element ")
while (node != nil)
print("\n ", node.n.first ," ", node.n.second)
node = node.next
end

print("\n")
end

end

class HuffmanCodes
#  Display Huffman code
def printTree(node, result)
if (node == nil)
return
end

if (node.left == nil && node.right == nil)
print(" ", node.second ," ", result ,"\n")
return
end

self.printTree(node.left, result+"0")
self.printTree(node.right, result+"1")
end

#  Construct Huffman Code Tree
def buildHuffmanCodes(value, frequency, n)
q = PriorityQueue.new()
root = nil
n1 = nil
n2 = nil
#  First add all elements into priority queue
i = 0
while (i < n)
root = TreeNode.new(frequency[i], value[i])
q.enQueue(root)
i += 1
end

#  printQdata(q)
#  Execute loop until the priority queue contains more than 1 node
while (q.isSize() > 1)
#  Get first smallest node
n1 = q.peek()
# Remove a front element
q.deQueue()
#  Get second smallest node
n2 = q.peek()
#  Remove a front element
q.deQueue()
#  Make new node using two smallest node
root = TreeNode.new(n1.first + n2.first, ' ')
#  Add new node into priority queue
q.enQueue(root)
#  Set left and right child
root.left = n1
root.right = n2
end

q.deQueue()
return root
end

# Get valid value
def actualValue(num)
if (num >= 0 && num <= 9)
return ((num + ('0'.ord)).chr).to_s
else
return ((num - 10 + ('A'.ord)).chr).to_s
end

end

# Display binary value
def printBinary(num)
if (num == 0)
print("0\n")
return
end

n = num
# This is used to store result
result = ""
# Transform decimal to other base
while (n > 0)
result = (self.actualValue(n % 2)) + result
n /= 2
end

print(result ,"\n")
end

#  We creating custom map functionality using linked list
#  This function are sorted insert element by value
def insertByValue(map, key, length)
element = MapElement.new(key, length)
if (element == nil)
print("\n Memory overflow to Create map element")
return
end

if (map.start == nil)
#  First node of map
map.start = element
elsif(length < map.start.value)
element.next = map.start
map.start = element
else
auxiliary = map.start
#  Add new element to its proper position
while (auxiliary != nil && auxiliary.next != nil && auxiliary.next.value <= length)
auxiliary = auxiliary.next
end

element.next = auxiliary.next
auxiliary.next = element
end

end

#  Get the Huffman code
def getCode(node, m, n)
if (node == nil)
return
end

if (node.left == nil && node.right == nil)
self.insertByValue(m, node.second, n)
return
end

self.getCode(node.left, m, n + 1)
self.getCode(node.right, m, n + 1)
end

#  Handles the request of printing canonical huffman code
def printCanonicalCode(root)
if (root == nil)
return
else
m = MyMap.new()
#  Get hamming code
self.getCode(root, m, 0)
auxiliary = m.start
auxiliary = m.start
code = -1
length = auxiliary.value
#  Iterating elements of map
while (auxiliary != nil)
#  Calculate canonical huffman code
code = (code + 1) << (auxiliary.value - length)
print(" ", auxiliary.key ," : ")
#  Display binary value
self.printBinary(code)
length = auxiliary.value
auxiliary = auxiliary.next
end

end

end

end

def main()
value = ['a', 'b', 'c', 'd', 'e', 'f', 'g']
frequency = [31, 54, 15, 4, 23, 52, 21]
n = frequency.length
print("Huffman Codes")
#  Finally find canonical huffman code
print("\n Canonical huffman code \n")
end

main()``````

#### Output

``````Huffman Codes d 0000
c 0001
g 001
f 01
b 10
e 110
a 111

Canonical huffman code
f : 0
b : 1
g : 100
e : 101
a : 110
d : 1110
c : 1111
``````
``````/*
Scala Program
Canonical Huffman Coding
*/
class TreeNode(var first: Int , var second: Character , var left: TreeNode , var right: TreeNode)
{
def this(first: Int, second: Char)
{
this(first, second, null, null);
}
}
class QNode(var n: TreeNode , var next: QNode , var prev: QNode)
{
def this(n: TreeNode)
{
this(n, null, null);
}
}
class MapElement(var key: Character , var value: Int , var next: MapElement)
{
def this(key: Char, value: Int)
{
this(key, value, null);
}
};
// Create custom map
class MyMap(var start: MapElement)
{
def this()
{
this(null);
}
};
class PriorityQueue(var front: QNode , var rear: QNode , var size: Int)
{
def this()
{
this(null, null, 0);
}
// Add a node into queue Priority queue
def enQueue(auxiliary: TreeNode): Unit = {
//Create a dynamic node
var node: QNode = new QNode(auxiliary);
node.n = auxiliary;
if (this.front == null)
{
// When adding a first node of queue
this.front = node;
this.rear = node;
}
else if (this.front.n.first >= auxiliary.first)
{
// Add node at beginning position
node.next = this.front;
this.front.prev = node;
this.front = node;
}
else if (this.rear.n.first <= auxiliary.first)
{
// Add node at last position
node.prev = this.rear;
this.rear.next = node;
this.rear = node;
}
else
{
var temp: QNode = this.front;
// Find the location of inserting priority node
while (temp.n.first < auxiliary.first)
{
temp = temp.next;
}
node.next = temp;
node.prev = temp.prev;
temp.prev = node;
if (node.prev != null)
{
node.prev.next = node;
}
}
this.size = this.size + 1;
}
def isEmpty(): Boolean = {
if (this.size == 0)
{
return true;
}
else
{
return false;
}
}
// Get a front element of queue
def peek(): TreeNode = {
if (this.isEmpty() == true)
{
// When Queue is empty
print("\n Empty Queue \n");
return null;
}
else
{
return this.front.n;
}
}
def isSize(): Int = {
return this.size;
}
// Remove a front node of a queue
def deQueue(): Unit = {
if (this.isEmpty() == false)
{
var temp: QNode = this.front;
temp.n = null;
if (this.front == this.rear)
{
// When queue contains only one node
this.rear = null;
this.front = null;
}
else
{
this.front = this.front.next;
this.front.prev = null;
}
// Change queue size
this.size -= 1;
}
}
// Print elements of queue
def printQdata(): Unit = {
var node: QNode = this.front;
print("\n Queue Element ");
while (node != null)
{
print("\n " + node.n.first + " " + node.n.second);
node = node.next;
}
print("\n");
}
}
class HuffmanCodes
{
// Display Huffman code
def printTree(node: TreeNode, result: String): Unit = {
if (node == null)
{
return;
}
if (node.left == null && node.right == null)
{
print(" " + node.second + " " + result + "\n");
return;
}
this.printTree(node.left, result + "0");
this.printTree(node.right, result + "1");
}
// Construct Huffman Code Tree
def buildHuffmanCodes(value: Array[Character], frequency: Array[Int], n: Int): TreeNode = {
var q: PriorityQueue = new PriorityQueue();
var root: TreeNode = null;
var n1: TreeNode = null;
var n2: TreeNode = null;
// First add all elements into priority queue
var i: Int = 0;
while (i < n)
{
root = new TreeNode(frequency(i), value(i));
q.enQueue(root);
i += 1;
}
// printQdata(q);
// Execute loop until the priority queue contains more than 1 node
while (q.isSize() > 1)
{
// Get first smallest node
n1 = q.peek();
//Remove a front element
q.deQueue();
// Get second smallest node
n2 = q.peek();
// Remove a front element
q.deQueue();
// Make new node using two smallest node
root = new TreeNode(n1.first + n2.first, ' ');
// Add new node into priority queue
q.enQueue(root);
// Set left and right child
root.left = n1;
root.right = n2;
}
q.deQueue();
return root;
}
//Get valid value
def actualValue(num: Int): Char = {
if (num >= 0 && num <= 9)
{
return ((num + '0')).toChar;
}
else
{
return ((num - 10 + 'A')).toChar;
}
}
//Display binary value
def printBinary(num: Int): Unit = {
if (num == 0)
{
print("0\n");
return;
}
var n: Int = num;
//This is used to store result
var result: String = "";
//Transform decimal to other base
while (n > 0)
{
result = ""+ (this.actualValue(n % 2)) + result;
n = (n / 2).toInt;
}
print(result + "\n");
}
// We creating custom map functionality using linked list
// This function are sorted insert element by value
def insertByValue(map: MyMap, key: Char, length: Int): Unit = {
var element: MapElement = new MapElement(key, length);
if (element == null)
{
print("\n Memory overflow to Create map element");
return;
}
if (map.start == null)
{
// First node of map
map.start = element;
}
else if (length < map.start.value)
{
element.next = map.start;
map.start = element;
}
else
{
var auxiliary: MapElement = map.start;
// Add new element to its proper position
while (auxiliary != null && auxiliary.next != null && auxiliary.next.value <= length)
{
auxiliary = auxiliary.next;
}
element.next = auxiliary.next;
auxiliary.next = element;
}
}
// Get the Huffman code
def getCode(node: TreeNode, m: MyMap, n: Int): Unit = {
if (node == null)
{
return;
}
if (node.left == null && node.right == null)
{
this.insertByValue(m, node.second, n);
return;
}
this.getCode(node.left, m, n + 1);
this.getCode(node.right, m, n + 1);
}
// Handles the request of printing canonical huffman code
def printCanonicalCode(root: TreeNode): Unit = {
if (root == null)
{
return;
}
else
{
var m: MyMap = new MyMap();
// Get hamming code
this.getCode(root, m, 0);
var auxiliary: MapElement = m.start;
auxiliary = m.start;
var code: Int = -1;
var length: Int = auxiliary.value;
// Iterating elements of map
while (auxiliary != null)
{
// Calculate canonical huffman code
code = (code + 1) << (auxiliary.value - length);
print(" " + auxiliary.key + " : ");
// Display binary value
this.printBinary(code);
length = auxiliary.value;
auxiliary = auxiliary.next;
}
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: HuffmanCodes = new HuffmanCodes();
var value: Array[Character] = Array('a', 'b', 'c', 'd', 'e', 'f', 'g');
var frequency: Array[Int] = Array(31, 54, 15, 4, 23, 52, 21);
var n: Int = frequency.length;
var root: TreeNode = task.buildHuffmanCodes(value, frequency, n);
print("Huffman Codes");
// Finally find canonical huffman code
print("\n Canonical huffman code \n");
}
}``````

#### Output

``````Huffman Codes d 0000
c 0001
g 001
f 01
b 10
e 110
a 111

Canonical huffman code
f : 0
b : 1
g : 100
e : 101
a : 110
d : 1110
c : 1111``````
``````/*
Swift 4 Program
Canonical Huffman Coding
*/
class TreeNode
{
var first: Int;
var second: Character;
var left: TreeNode? ;
var right: TreeNode? ;
init(_ first: Int, _ second: Character)
{
self.first = first;
self.second = second;
self.left = nil;
self.right = nil;
}
}
class QNode
{
var n: TreeNode? ;
var next: QNode? ;
var prev: QNode? ;
init(_ n: TreeNode? )
{
self.n = n;
self.prev = nil;
self.next = nil;
}
}
class MapElement
{
var key: Character;
var value: Int;
var next: MapElement? ;
init(_ key: Character, _ value: Int)
{
self.key = key;
self.value = value;
self.next = nil;
}
};
// Create custom map
class MyMap
{
var start: MapElement? ;
init()
{
self.start = nil;
}
};
class PriorityQueue
{
var front: QNode? ;
var rear: QNode? ;
var size: Int;
init()
{
self.front = nil;
self.rear = nil;
self.size = 0;
}
// Add a node into queue Priority queue
func enQueue(_ auxiliary: TreeNode? )
{
//Create a dynamic node
let node: QNode? = QNode(auxiliary);
node!.n = auxiliary;
if (self.front == nil)
{
// When adding a first node of queue
self.front = node;
self.rear = node;
}
else if (self.front!.n!.first >= auxiliary!.first)
{
// Add node at beginning position
node!.next = self.front;
self.front!.prev = node;
self.front = node;
}
else if (self.rear!.n!.first <= auxiliary!.first)
{
// Add node at last position
node!.prev = self.rear;
self.rear!.next = node;
self.rear = node;
}
else
{
var temp: QNode? = self.front;
// Find the location of inserting priority node
while (temp!.n!.first < auxiliary!.first)
{
temp = temp!.next;
}
node!.next = temp;
node!.prev = temp!.prev;
temp!.prev = node;
if (node!.prev  != nil)
{
node!.prev!.next = node;
}
}
self.size = self.size + 1;
}
func isEmpty()->Bool
{
if (self.size == 0)
{
return true;
}
else
{
return false;
}
}
// Get a front element of queue
func peek()->TreeNode?
{
if (self.isEmpty() == true)
{
// When Queue is empty
print("\n Empty Queue ");
return nil;
}
else
{
return self.front!.n;
}
}
func isSize()->Int
{
return self.size;
}
// Remove a front node of a queue
func deQueue()
{
if (self.isEmpty() == false)
{
let temp: QNode? = self.front;
temp!.n = nil;
if (self.front === self.rear)
{
// When queue contains only one node
self.rear = nil;
self.front = nil;
}
else
{
self.front = self.front!.next;
self.front!.prev = nil;
}
// Change queue size
self.size -= 1;
}
}
// Print elements of queue
func printQdata()
{
var node: QNode? = self.front;
print("\n Queue Element ", terminator: "");
while (node  != nil)
{
print("\n ", node!.n!.first ," ", node!.n!.second, terminator: "");
node = node!.next;
}
print(terminator: "\n");
}
}
class HuffmanCodes
{
// Display Huffman code
func printTree(_ node: TreeNode? , _ result : String)
{
if (node == nil)
{
return;
}
if (node!.left == nil && node!.right == nil)
{
print(" ", node!.second ," ", result );
return;
}
self.printTree(node!.left, result+"0");
self.printTree(node!.right, result+"1");
}
// Construct Huffman Code Tree
func buildHuffmanCodes(_ value: [Character], _ frequency: [Int], _ n: Int)->TreeNode?
{
let q: PriorityQueue = PriorityQueue();
var root: TreeNode? = nil;
var n1: TreeNode? = nil;
var n2: TreeNode? = nil;
// First add all elements into priority queue
var i: Int = 0;
while (i < n)
{
root = TreeNode(frequency[i], value[i]);
q.enQueue(root);
i += 1;
}
// printQdata(q);
// Execute loop until the priority queue contains more than 1 node
while (q.isSize() > 1)
{
// Get first smallest node
n1 = q.peek();
//Remove a front element
q.deQueue();
// Get second smallest node
n2 = q.peek();
// Remove a front element
q.deQueue();
// Make new node using two smallest node
root = TreeNode(n1!.first + n2!.first, " ");
// Add new node into priority queue
q.enQueue(root);
// Set left and right child
root!.left = n1;
root!.right = n2;
}
q.deQueue();
return root;
}
//Get valid value
func actualValue(_ num: Int)->String
{
if (num >= 0 && num <= 9)
{
return String(UnicodeScalar(UInt8( num + Int(UnicodeScalar("0")!.value ))));
}
else
{

return String(UnicodeScalar(UInt8((num - 10) + Int(UnicodeScalar("A")!.value ))));
}
}
//Display binary value
func printBinary(_ num: Int)
{
if (num == 0)
{
print("0");
return;
}
var n: Int = num;
//This is used to store result
var result: String = "";
//Transform decimal to other base
while (n > 0)
{
result = (self.actualValue(n % 2)) + result;
n /= 2;
}
print(result );
}
// We creating custom map functionality using linked list
// This function are sorted insert element by value
func insertByValue(_ map: MyMap? , _ key : Character, _ length: Int)
{
let element: MapElement? = MapElement(key, length);
if (element == nil)
{
print("\n Memory overflow to Create map element", terminator: "");
return;
}
if (map!.start == nil)
{
// First node of map
map!.start = element;
}
else if (length < map!.start!.value)
{
element!.next = map!.start;
map!.start = element;
}
else
{
var auxiliary: MapElement? = map!.start;
// Add new element to its proper position
while (auxiliary  != nil && auxiliary!.next  != nil
&& auxiliary!.next!.value <= length)
{
auxiliary = auxiliary!.next;
}
element!.next = auxiliary!.next;
auxiliary!.next = element;
}
}
// Get the Huffman code
func getCode(_ node: TreeNode? , _ m : MyMap? , _ n : Int)
{
if (node == nil)
{
return;
}
if (node!.left == nil && node!.right == nil)
{
self.insertByValue(m, node!.second, n);
return;
}
self.getCode(node!.left, m, n + 1);
self.getCode(node!.right, m, n + 1);
}
// Handles the request of printing canonical huffman code
func printCanonicalCode(_ root: TreeNode? )
{
if (root == nil)
{
return;
}
else
{
let m: MyMap? = MyMap();
// Get hamming code
self.getCode(root, m, 0);
var auxiliary: MapElement? = m!.start;
auxiliary = m!.start;
var code: Int = -1;
var length: Int = auxiliary!.value;
// Iterating elements of map
while (auxiliary  != nil)
{
// Calculate canonical huffman code
code = (code + 1) << (auxiliary!.value - length);
print(" ", auxiliary!.key ," : ", terminator: "");
// Display binary value
self.printBinary(code);
length = auxiliary!.value;
auxiliary = auxiliary!.next;
}
}
}
}
func main()
{
let value: [Character] = ["a", "b", "c", "d", "e", "f", "g"];
let frequency: [Int] = [31, 54, 15, 4, 23, 52, 21];
let n: Int = frequency.count;
let root: TreeNode? = task.buildHuffmanCodes(value, frequency, n);
print("Huffman Codes", terminator: "");
// Finally find canonical huffman code
print("\n Canonical huffman code ");
}
main();``````

#### Output

``````Huffman Codes  d   0000
c   0001
g   001
f   01
b   10
e   110
a   111

Canonical huffman code
f  : 0
b  : 1
g  : 100
e  : 101
a  : 110
d  : 1110
c  : 1111``````
``````/*
Kotlin Program
Canonical Huffman Coding
*/
class TreeNode
{
var first: Int;
var second: Char;
var left: TreeNode ? ;
var right: TreeNode ? ;
constructor(first: Int, second: Char)
{
this.first = first;
this.second = second;
this.left = null;
this.right = null;
}
}
class QNode
{
var n: TreeNode ? ;
var next: QNode ? ;
var prev: QNode ? ;
constructor(n: TreeNode ? )
{
this.n = n;
this.prev = null;
this.next = null;
}
}
class MapElement
{
var key: Char;
var value: Int;
var next: MapElement ? ;
constructor(key: Char, value: Int)
{
this.key = key;
this.value = value;
this.next = null;
}
};
// Create custom map
class MyMap
{
var start: MapElement ? ;
constructor()
{
this.start = null;
}
};
class PriorityQueue
{
var front: QNode ? ;
var rear: QNode ? ;
var size: Int;
constructor()
{
this.front = null;
this.rear = null;
this.size = 0;
}
// Add a node into queue Priority queue
fun enQueue(auxiliary: TreeNode ): Unit
{
//Create a dynamic node
var node: QNode = QNode(auxiliary);
node.n = auxiliary;
if (this.front == null)
{
// When adding a first node of queue
this.front = node;
this.rear = node;
}
else if (this.front?.n!!.first >= auxiliary.first)
{
// Add node at beginning position
node.next = this.front;
this.front?.prev = node;
this.front = node;
}
else if (this.rear?.n!!.first <= auxiliary.first)
{
// Add node at last position
node.prev = this.rear;
this.rear?.next = node;
this.rear = node;
}
else
{
var temp: QNode ? = this.front;
// Find the location of inserting priority node
while (temp?.n!!.first < auxiliary.first)
{
temp = temp.next;
}
node.next = temp;
node.prev = temp.prev;
temp.prev = node;
if (node.prev != null)
{
node.prev?.next = node;
}
}
this.size = this.size + 1;
}
fun isEmpty(): Boolean
{
if (this.size == 0)
{
return true;
}
else
{
return false;
}
}
// Get a front element of queue
fun peek(): TreeNode ?
{
if (this.isEmpty() == true)
{
// When Queue is empty
print("\n Empty Queue \n");
return null;
}
else
{
return this.front?.n;
}
}
fun isSize(): Int
{
return this.size;
}
// Remove a front node of a queue
fun deQueue(): Unit
{
if (this.isEmpty() == false)
{
var temp: QNode ? = this.front;
temp?.n = null;
if (this.front == this.rear)
{
// When queue contains only one node
this.rear = null;
this.front = null;
}
else
{
this.front = this.front?.next;
this.front?.prev = null;
}
// Change queue size
this.size -= 1;
}
}
// Print elements of queue
fun printQdata(): Unit
{
var node: QNode ? = this.front;
print("\n Queue Element ");
while (node != null)
{
print("\n " + node.n?.first + " " + node.n?.second);
node = node.next;
}
print("\n");
}
}
class HuffmanCodes
{
// Display Huffman code
fun printTree(node: TreeNode ? , result : String): Unit
{
if (node == null)
{
return;
}
if (node.left == null && node.right == null)
{
print(" " + node.second + " " + result + "\n");
return;
}
this.printTree(node.left, result + "0");
this.printTree(node.right, result + "1");
}
// Construct Huffman Code Tree
fun buildHuffmanCodes(value: Array <Char> , frequency: Array < Int > , n: Int): TreeNode ?
{
var q: PriorityQueue = PriorityQueue();
var root: TreeNode ? = null;
var n1: TreeNode ? ;
var n2: TreeNode ? ;
// First add all elements into priority queue
var i: Int = 0;
while (i < n)
{
root = TreeNode(frequency[i], value[i]);
q.enQueue(root);
i += 1;
}
// printQdata(q);
// Execute loop until the priority queue contains more than 1 node
while (q.isSize() > 1)
{
// Get first smallest node
n1 = q.peek();
//Remove a front element
q.deQueue();
// Get second smallest node
n2 = q.peek();
// Remove a front element
q.deQueue();
// Make new node using two smallest node
root = TreeNode(n1!!.first + n2!!.first, ' ');
// Add new node into priority queue
q.enQueue(root);
// Set left and right child
root.left = n1;
root.right = n2;
}
q.deQueue();
return root;
}
//Get valid value
fun actualValue(num: Int): Char
{
if (num >= 0 && num <= 9)
{
return (num + '0'.toInt()).toChar();
}
else
{
return (num - 10 + 'A'.toInt()).toChar();
}
}
//Display binary value
fun printBinary(num: Int): Unit
{
if (num == 0)
{
print("0\n");
return;
}
var n: Int = num;
//This is used to store result
var result: String = "";
//Transform decimal to other base
while (n > 0)
{
result = (this.actualValue(n % 2)) + result;
n /= 2;
}
print(result + "\n");
}
// We creating custom map functionality using linked list
// This function are sorted insert element by value
fun insertByValue(map: MyMap ? , key : Char, length: Int): Unit
{
var element: MapElement = MapElement(key, length);

if (map?.start == null)
{
// First node of map
map?.start = element;
}
else if (length < map.start!!.value)
{
element.next = map.start;
map.start = element;
}
else
{
var auxiliary: MapElement ? = map.start;
// Add new element to its proper position
while (auxiliary != null && auxiliary.next != null
&& auxiliary.next!!.value <= length)
{
auxiliary = auxiliary.next;
}
element.next = auxiliary?.next;
auxiliary?.next = element;
}
}
// Get the Huffman code
fun getCode(node: TreeNode ? , m : MyMap ? , n : Int): Unit
{
if (node == null)
{
return;
}
if (node.left == null && node.right == null)
{
this.insertByValue(m, node.second, n);
return;
}
this.getCode(node.left, m, n + 1);
this.getCode(node.right, m, n + 1);
}
// Handles the request of printing canonical huffman code
fun printCanonicalCode(root: TreeNode ? ): Unit
{
if (root == null)
{
return;
}
else
{
var m: MyMap = MyMap();
// Get hamming code
this.getCode(root, m, 0);
var auxiliary: MapElement ? = m.start;

var code: Int = -1;
var length: Int = auxiliary!!.value;
// Iterating elements of map
while (auxiliary != null)
{
// Calculate canonical huffman code
code = (code + 1) shl (auxiliary.value - length);
print(" " + auxiliary.key + " : ");
// Display binary value
this.printBinary(code);
length = auxiliary.value;
auxiliary = auxiliary.next;
}
}
}
}
fun main(args: Array < String > ): Unit
{
var value: Array < Char > = arrayOf('a', 'b', 'c', 'd', 'e', 'f', 'g');
var frequency: Array < Int > = arrayOf(31, 54, 15, 4, 23, 52, 21);
var n: Int = frequency.count();
var root: TreeNode ? = task.buildHuffmanCodes(value, frequency, n);
print("Huffman Codes");
// Finally find canonical huffman code
print("\n Canonical huffman code \n");
}``````

#### Output

``````Huffman Codes d 0000
c 0001
g 001
f 01
b 10
e 110
a 111

Canonical huffman code
f : 0
b : 1
g : 100
e : 101
a : 110
d : 1110
c : 1111``````

## Resultant Output Explanation

The code outputs the following:

``````Huffman code
d 0000
c 0001
g 001
f 01
b 10
e 110
a 111
Canonical huffman code
f : 0
b : 1
g : 100
e : 101
a : 110
d : 1110
c : 1111``````
1. Display the Huffman codes generated from the Huffman tree.
2. Display the Canonical Huffman codes derived from the Huffman codes.

## Time Complexity

1. Building Huffman Tree: O(n log n) - Constructing the Huffman tree using a priority queue.
2. Generating Huffman Codes: O(n) - Generating Huffman codes for each character.
3. Constructing Custom Map: O(n) - Creating the custom map using sorted insertions.
4. Printing Canonical Huffman Codes: O(n) - Printing Canonical Huffman codes.

The overall time complexity of this solution is mainly dominated by building the Huffman tree and generating Huffman codes, both of which are O(n log n), where `n` is the number of characters.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.