Skip to main content

Huffman coding using priority queue

Huffman Coding

Here given code implementation process.

/*
    C Program 
    Huffman coding using priority queue
*/
#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;
};
// 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");
}
// 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);
}
// 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;
}
int main(int argc, char
	const *argv[])
{
	char value[] = {
		'a' , 'b' , 'c' , 'd' , 'e' , 'f' , 'g'
	};
	int frequency[] = {
		16 , 8 , 19 , 32 , 21 , 10 , 5
	};
	int n = sizeof(frequency) / sizeof(frequency[0]);
	char result[n + 1];
	struct TreeNode *root = buildHuffmanCodes(value, frequency, n);
	printTree(root, result, 0);
	return 0;
}

Output

 e 00
 f 010
 g 0110
 b 0111
 d 10
 a 110
 c 111
/*
    Java Program 
    Implement priority queue with pair
*/
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 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("\n " + node.second + " " + result);
			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;
	}
	public static void main(String[] args)
	{
		HuffmanCodes task = new HuffmanCodes();
		char[] value = {
			'a' , 'b' , 'c' , 'd' , 'e' , 'f' , 'g'
		};
		int[] frequency = {
			16 , 8 , 19 , 32 , 21 , 10 , 5
		};
		int n = frequency.length;
		TreeNode root = task.buildHuffmanCodes(value, frequency, n);
		task.printTree(root, "");
	}
}

Output

 e 00
 f 010
 g 0110
 b 0111
 d 10
 a 110
 c 111
// Include header file
#include <iostream>

using namespace std;
/*
    C++ Program 
    Implement priority queue with pair
*/
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 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;
			}
          	temp->n = NULL;
          	delete temp;
			// 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 << "\n " << node->second << " " << result;
				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;
	}
};
int main()
{
	HuffmanCodes task = HuffmanCodes();
	char value[] = {
		'a' , 'b' , 'c' , 'd' , 'e' , 'f' , 'g'
	};
	int frequency[] = {
		16 , 8 , 19 , 32 , 21 , 10 , 5
	};
	int n = sizeof(frequency) / sizeof(frequency[0]);
	TreeNode *root = task.buildHuffmanCodes(value, frequency, n);
	task.printTree(root, "");
	return 0;
}

Output

 e 00
 f 010
 g 0110
 b 0111
 d 10
 a 110
 c 111
// Include namespace system
using System;
/*
    C# Program 
    Implement priority queue with pair
*/
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 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("\n " + node.second + " " + result);
			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);
		}
		// q.printQdata();
		// 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;
	}
	public static void Main(String[] args)
	{
		HuffmanCodes task = new HuffmanCodes();
		char[] value = {
			'a' , 'b' , 'c' , 'd' , 'e' , 'f' , 'g'
		};
		int[] frequency = {
			16 , 8 , 19 , 32 , 21 , 10 , 5
		};
		int n = frequency.Length;
		TreeNode root = task.buildHuffmanCodes(value, frequency, n);
		task.printTree(root, "");
	}
}

Output

 e 00
 f 010
 g 0110
 b 0111
 d 10
 a 110
 c 111
<?php
/*
    Php Program 
    Implement priority queue with pair
*/
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 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 "\n ". $node->second ." ". $result;
			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);
		}
		// q.printQdata();
		// 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;
	}
}

function main()
{
	$task = new HuffmanCodes();
	$value = array('a', 'b', 'c', 'd', 'e', 'f', 'g');
	$frequency = array(16, 8, 19, 32, 21, 10, 5);
	$n = count($frequency);
	$root = $task->buildHuffmanCodes($value, $frequency, $n);
	$task->printTree($root, "");
}
main();

Output

 e 00
 f 010
 g 0110
 b 0111
 d 10
 a 110
 c 111
/*
    Node Js Program 
    Implement priority queue with pair
*/
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 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("\n " + node.second + " " + result);
			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);
		}
		// q.printQdata();
		// 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;
	}
}

function main()
{
	var task = new HuffmanCodes();
	var value = ['a', 'b', 'c', 'd', 'e', 'f', 'g'];
	var frequency = [16, 8, 19, 32, 21, 10, 5];
	var n = frequency.length;
	var root = task.buildHuffmanCodes(value, frequency, n);
	task.printTree(root, "");
}
main();

Output

 e 00
 f 010
 g 0110
 b 0111
 d 10
 a 110
 c 111
#  Python 3 Program 
#  Implement priority queue with pair

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 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("\n ", node.second ," ", result, end = "")
			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
		i = 0
		#  First add all elements into priority queue
		while (i < n) :
			root = TreeNode(frequency[i], value[i])
			q.enQueue(root)
			i += 1
		
		#  q.printQdata()
		#  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
	

def main() :
	task = HuffmanCodes()
	value = ['a', 'b', 'c', 'd', 'e', 'f', 'g']
	frequency = [16, 8, 19, 32, 21, 10, 5]
	n = len(frequency)
	root = task.buildHuffmanCodes(value, frequency, n)
	task.printTree(root, "")

if __name__ == "__main__": main()

Output

  e   00
  f   010
  g   0110
  b   0111
  d   10
  a   110
  c   111
#  Ruby Program 
#  Implement priority queue with pair

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 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("\n ", node.second ," ", result)
			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
		i = 0
		#  First add all elements into priority queue
		while (i < n) 
			root = TreeNode.new(frequency[i], value[i])
			q.enQueue(root)
			i += 1
		end

		#  q.printQdata()
		#  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

end

def main() 
	task = HuffmanCodes.new()
	value = ['a', 'b', 'c', 'd', 'e', 'f', 'g']
	frequency = [16, 8, 19, 32, 21, 10, 5]
	n = frequency.length
	root = task.buildHuffmanCodes(value, frequency, n)
	task.printTree(root, "")
end

main()

Output

 e 00
 f 010
 g 0110
 b 0111
 d 10
 a 110
 c 111
/*
    Scala Program 
    Implement priority queue with pair
*/
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 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("\n " + node.second + " " + result);
			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;
		var i: Int = 0;
		// First add all elements into priority queue
		while (i < n)
		{
			root = new TreeNode(frequency(i), value(i));
			q.enQueue(root);
			i += 1;
		}
		// q.printQdata();
		// 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;
	}
}
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(16, 8, 19, 32, 21, 10, 5);
		var n: Int = frequency.length;
		var root: TreeNode = task.buildHuffmanCodes(value, frequency, n);
		task.printTree(root, "");
	}
}

Output

 e 00
 f 010
 g 0110
 b 0111
 d 10
 a 110
 c 111
/*
    Swift 4 Program 
    Implement priority queue with pair
*/
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 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("\n ", node!.second ," ", result, terminator: "");
			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;
		var i: Int = 0;
		// First add all elements into priority queue
		while (i < n)
		{
			root = TreeNode(frequency[i], value[i]);
			q.enQueue(root);
			i += 1;
		}
		// q.printQdata();
		// 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;
	}
}
func main()
{
	let task: HuffmanCodes = HuffmanCodes();
	let value: [Character] = ["a", "b", "c", "d", "e", "f", "g"];
	let frequency: [Int] = [16, 8, 19, 32, 21, 10, 5];
	let n: Int = frequency.count;
	let root: TreeNode? = task.buildHuffmanCodes(value, frequency, n);
	task.printTree(root, "");
}
main();

Output

  e   00
  f   010
  g   0110
  b   0111
  d   10
  a   110
  c   111
/*
    Kotlin Program 
    Implement priority queue with pair
*/
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 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("\n " + node.second + " " + result);
			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 ? ;
		var i: Int = 0;
		// First add all elements into priority queue
		while (i < n)
		{
			root = TreeNode(frequency[i], value[i]);
			q.enQueue(root);
			i += 1;
		}
		// q.printQdata();
		// 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;
	}
}
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(16, 8, 19, 32, 21, 10, 5);
	var n: Int = frequency.count();
	var root: TreeNode ? = task.buildHuffmanCodes(value, frequency, n);
	task.printTree(root, "");
}

Output

 e 00
 f 010
 g 0110
 b 0111
 d 10
 a 110
 c 111
Last updated on by Kalkicode




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.

New Comment