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

Define necessary structures for nodes, queues, and maps.
Implement methods to create new nodes, new queues, and manage the priority queue.
Implement methods to create a custom map, insert elements, and generate Huffman codes.
Implement methods to print binary numbers and print Canonical Huffman codes.
Implement methods to print Huffman codes and handle printing in the main tree traversal.
Build the Huffman tree using the given frequencies.
Print Huffman codes.
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;
			}
			// Add node
			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)
	{
		// Add left node value
		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;
            }
            // Add node
            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)
        {
            // Add left node value
            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)
    {
        HuffmanCodes task = new HuffmanCodes();
        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");
        task.printTree(root, "");

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

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;
			}
			// Add node
			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)
		{
			// Add left node value
			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()
{
	HuffmanCodes task = HuffmanCodes();
	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";
	task.printTree(root, "");
	// Finally find canonical huffman code
	cout << "\n Canonical huffman code \n";
	task.printCanonicalCode(root);
	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;
			}
			// Add node
			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)
		{
			// Add left node value
			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)
	{
		HuffmanCodes task = new HuffmanCodes();
		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");
		task.printTree(root, "");
		// Finally find canonical huffman code
		Console.Write("\n Canonical huffman code \n");
		task.printCanonicalCode(root);
	}
}

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;
			}
			// Add node
			$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)
		{
			// Add left node value
			$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()
{
	$task = new HuffmanCodes();
	$value = array('a', 'b', 'c', 'd', 'e', 'f', 'g');
	$frequency = array(31, 54, 15, 4, 23, 52, 21);
	$n = count($frequency);
	$root = $task->buildHuffmanCodes($value, $frequency, $n);
	echo "Huffman Codes";
	$task->printTree($root, "");
	// Finally find canonical huffman code
	echo "\n Canonical huffman code \n";
	$task->printCanonicalCode($root);
}
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;
			}
			// Add node
			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)
		{
			// Add left node value
			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 task = new HuffmanCodes();
	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");
	task.printTree(root, "");
	// Finally find canonical huffman code
	process.stdout.write("\n Canonical huffman code \n");
	task.printCanonicalCode(root);
}
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
			
			#  Add node
			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) :
			#  Add left node value
			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() :
	task = HuffmanCodes()
	value = ['a', 'b', 'c', 'd', 'e', 'f', 'g']
	frequency = [31, 54, 15, 4, 23, 52, 21]
	n = len(frequency)
	root = task.buildHuffmanCodes(value, frequency, n)
	print("Huffman Codes", end = "\n")
	task.printTree(root, "")
	#  Finally find canonical huffman code
	print("\n Canonical huffman code ")
	task.printCanonicalCode(root)

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_reader :first, :second, :left, :right
	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_reader :n, :next, :prev
	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_reader :key, :value, :next
	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_reader :start
	attr_accessor :start
 
	
	def initialize() 
		self.start = nil
	end

end

class PriorityQueue  
	# Define the accessor and reader of class PriorityQueue  
	attr_reader :front, :rear, :size
	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

			#  Add node
			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) 
			#  Add left node value
			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() 
	task = HuffmanCodes.new()
	value = ['a', 'b', 'c', 'd', 'e', 'f', 'g']
	frequency = [31, 54, 15, 4, 23, 52, 21]
	n = frequency.length
	root = task.buildHuffmanCodes(value, frequency, n)
	print("Huffman Codes")
	task.printTree(root, "")
	#  Finally find canonical huffman code
	print("\n Canonical huffman code \n")
	task.printCanonicalCode(root)
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;
			}
			// Add node
			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)
		{
			// Add left node value
			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");
		task.printTree(root, "");
		// Finally find canonical huffman code
		print("\n Canonical huffman code \n");
		task.printCanonicalCode(root);
	}
}

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;
			}
			// Add node
			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)
		{
			// Add left node value
			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 task: HuffmanCodes = HuffmanCodes();
	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: "");
	task.printTree(root, "");
	// Finally find canonical huffman code
	print("\n Canonical huffman code ");
	task.printCanonicalCode(root);
}
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;
			}
			// Add node
			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)
		{
			// Add left node value
			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 task: HuffmanCodes = HuffmanCodes();
	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");
	task.printTree(root, "");
	// Finally find canonical huffman code
	print("\n Canonical huffman code \n");
	task.printCanonicalCode(root);
}

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

Display the Huffman codes generated from the Huffman tree.
Display the Canonical Huffman codes derived from the Huffman codes.

Time Complexity

Building Huffman Tree: O(n log n) - Constructing the Huffman tree using a priority queue.
Generating Huffman Codes: O(n) - Generating Huffman codes for each character.
Constructing Custom Map: O(n) - Creating the custom map using sorted insertions.
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.

Canonical Huffman Coding

Problem Statement

Explanation with an Example

Idea to Solve

Pseudocode

Algorithm Explanation

Code Solution

Output

Output

Output

Output

Output

Output

Output

Output

Output

Output

Output

Resultant Output Explanation

Time Complexity

Comment

New Comment