Posted on by Kalkicode
Code Queue

# Huffman coding using priority queue

The problem tackled about implementing Huffman coding using a priority queue. Huffman coding is a lossless data compression algorithm used to encode characters based on their frequencies in a given text. It assigns shorter codes to characters that occur more frequently, resulting in efficient compression.

## Problem Statement

The task involves constructing a Huffman coding tree using a priority queue. Given a set of characters and their corresponding frequencies, the goal is to build a binary tree that represents the encoding scheme. Each leaf node of the tree corresponds to a character, and the path from the root to a leaf node represents the binary code for that character.

## Explanation with an Example

Imagine you have a set of characters {'a', 'b', 'c', 'd', 'e', 'f', 'g'} and their corresponding frequencies {16, 8, 19, 32, 21, 10, 5}. You want to construct a Huffman coding tree to assign binary codes to these characters based on their frequencies.

## Idea to Solve

To solve this problem, we use a priority queue to build the Huffman coding tree. We start by creating tree nodes for each character-frequency pair and enqueue them into the priority queue. In each iteration, we dequeue the two nodes with the lowest frequencies, create a new internal node, and enqueue it back into the priority queue. We repeat this process until there is only one node left in the priority queue, which becomes the root of the Huffman tree.

## Pseudocode

``````newTreeNode(frequency, character):
Create a new TreeNode `node`
Set `node` frequency to `frequency`
Set `node` character to `character`
Set `node` left and right child nodes to NULL
Return `node`

newPriorityQueue():
Create a new PriorityQueue `q`
Initialize `q` front and rear to NULL
Initialize `q` size to 0
Return `q`

enQueue(q, node):
Create a new QNode `qNode`
Set `qNode` node to `node`
Set `qNode` next and prev to NULL
... (enqueue logic to maintain priority order)
Increment `q` size

peek(q):
Return front node's data of `q`

deQueue(q):
Remove front node from `q`
Decrement `q` size

buildHuffmanCodes(value, frequency, n):
Create a new priority queue `q`
Create tree nodes for each character-frequency pair and enqueue them into `q`
Loop while `q` size is greater than 1:
Dequeue two nodes with lowest frequencies from `q`
Create a new internal node with combined frequency and enqueue it into `q`
Set the dequeued nodes as children of the internal node
Dequeue the final node from `q` and return it

printTree(node, result, n):
If node is leaf:
Print character and corresponding code
Return
Assign '0' to result[n] and recursively call printTree for left child
Assign '1' to result[n] and recursively call printTree for right child

Main:
Initialize arrays `value` and `frequency`
Get the number of characters `n`
Build Huffman coding tree using `buildHuffmanCodes`
Call `printTree` to print the characters and their Huffman codes``````

## Algorithm Explanation

1. Create tree nodes for characters and their frequencies.
2. Enqueue these nodes into a priority queue.
3. Build the Huffman coding tree using the priority queue:
• Dequeue two nodes with the lowest frequencies.
• Create a new internal node with combined frequency and enqueue it back.
• Set the dequeued nodes as children of the internal node.
4. Dequeue the final node from the priority queue.
5. Print the characters and their corresponding Huffman codes using the `printTree` function.

## Code Solution

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;
}
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;
}
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);
}
}``````

#### 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;
}
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);
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;
}
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);
}
}``````

#### 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;
}
\$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);
}
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;
}
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);
}
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

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() :
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)

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

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()
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)
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;
}
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);
}
}``````

#### 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;
}
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);
}
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;
}
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);
}``````

#### Output

`````` e 00
f 010
g 0110
b 0111
d 10
a 110
c 111``````

## Resultant Output Explanation

Each line represents a character and its corresponding Huffman code. For example, character 'e' has the Huffman code '00', character 'f' has '010', and so on.

## Time Complexity

1. Enqueue Operation: O(log n) - Inserting elements into the priority queue.
2. Build Huffman Codes: O(n log n) - Constructing the Huffman coding tree using the priority queue.
3. Print Tree: O(n) - Printing the Huffman codes for characters.

The overall time complexity of this solution is dominated by the `buildHuffmanCodes` operation, which is O(n log n), where `n` is the number of characters. The algorithm efficiently constructs the Huffman coding tree and assigns binary codes to characters based on their frequencies.

## 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.

Categories
Relative Post