Huffman Tree Example
The Huffman Tree, also known as Huffman Coding, is a popular algorithm used for data compression. It's an efficient way to represent characters in a way that minimizes the total number of bits needed to represent a given set of characters based on their frequencies. This algorithm was developed by David A. Huffman while he was a Ph.D. student at MIT, and it's widely used in various applications including file compression and encoding.
Problem Statement
The problem that the Huffman Tree algorithm solves is how to efficiently encode a set of characters into a binary format, where characters that appear more frequently are assigned shorter codes, and characters that appear less frequently are assigned longer codes. The main goal is to reduce the overall space required to store the data while ensuring that it can be uniquely decoded.
Example
Consider a simple example with the following characters and their frequencies:
Characters: a, b, c, d, e, f, g
Frequencies: 16, 8, 19, 32, 21, 10, 5
The huffman codes for each character based on the given frequencies. It's a mapping between characters and their corresponding binary codes.
e : 00
f : 010
g : 0110
b : 0111
d : 10
a : 110
c : 111
Idea to Solve
The idea is to build a binary tree in which the characters with lower frequencies are located towards the bottom while the characters with higher frequencies are closer to the top. The tree is constructed in such a way that each leaf node corresponds to a character, and the path from the root to the leaf node represents the binary code for that character. Characters with higher frequencies will have shorter paths and hence shorter codes.
Pseudocode
- Create a priority queue (min heap) of characters along with their frequencies.
- While there is more than one node in the queue: a. Remove two nodes with the lowest frequencies. b. Create a new internal node with a frequency equal to the sum of the two nodes' frequencies. c. Make the first removed node the left child and the second removed node the right child of the new node. d. Insert the new node back into the queue.
- The remaining node in the queue is the root of the Huffman Tree.
Algorithm Explanation
- Create a min heap to store nodes along with their frequencies.
- For each character and its frequency, create a tree node and insert it into the min heap.
- While the size of the min heap is greater than 1: a. Extract two nodes with the lowest frequencies from the heap. b. Create a new internal node with a frequency equal to the sum of the extracted nodes' frequencies. c. Set the extracted nodes as the left and right children of the new node. d. Insert the new node back into the min heap.
- The last remaining node in the min heap is the root of the Huffman Tree.
- Traverse the Huffman Tree to generate the Huffman codes for each character. Start from the root: a. If you move left, append '0' to the code. b. If you move right, append '1' to the code. c. When you reach a leaf node, print the character and its code.
- The printed codes are the Huffman codes for each character.
Code Solution
// C program
// Huffman Tree Example
#include <stdio.h>
#include <stdlib.h>
// Tree node
struct TreeNode
{
// Character element
char element;
// Element frequency
int freq;
// Left subtree
struct TreeNode *left;
// Right subtree
struct TreeNode *right;
};
// Min heap
struct MinHeap
{
int size;
int capacity;
// Use to collect record
struct TreeNode **record;
};
// Huffman Tree
struct HuffmanTree
{
struct TreeNode *root;
};
// Create and return new tree
struct HuffmanTree *newTree()
{
// Create a dynamic tree
struct HuffmanTree *tree = (struct HuffmanTree *) malloc(sizeof(struct HuffmanTree));
if (tree != NULL)
{
tree->root = NULL;
}
else
{
printf("Memory Overflow to Create tree Tree\n");
exit(0);
}
// Return new tree
return tree;
}
// Create new tree node
struct TreeNode *newNode(char element, int freq)
{
// Allocate memory of new nodes
struct TreeNode *node = (struct TreeNode *) malloc(sizeof(struct TreeNode));
if (node == NULL)
{
printf("Memory Overflow to Create tree node\n");
exit(0);
}
node->element = element;
node->freq = freq;
// set node child
node->left = NULL;
node->right = NULL;
return node;
}
struct MinHeap *createMinHeap(int capacity)
{
struct MinHeap *heap = (struct MinHeap *) malloc(sizeof(struct MinHeap));
if (heap == NULL)
{
printf("Memory Overflow to create Min Heap \n");
exit(0);
}
// Initial number of element
heap->size = 0;
// Allocate the memory of record element
heap->record = (struct TreeNode **) malloc(capacity *sizeof(struct TreeNode *));
// Set heap capacity
heap->capacity = capacity;
return heap;
}
void minHeapify(struct MinHeap *minHeap, int idx)
{
int smallest = idx;
// Left child
int left = 2 *idx + 1;
// Right child
int right = 2 *idx + 2;
if (left < minHeap->size && minHeap->record[left]->freq < minHeap->record[smallest]->freq)
{
smallest = left;
}
if (right < minHeap->size && minHeap->record[right]->freq < minHeap->record[smallest]->freq)
{
smallest = right;
}
if (smallest != idx)
{
struct TreeNode *temp = minHeap->record[smallest];
minHeap->record[smallest] = minHeap->record[idx];
minHeap->record[idx] = temp;
minHeapify(minHeap, smallest);
}
}
struct TreeNode *extractMin(struct MinHeap *minHeap)
{
struct TreeNode *temp = minHeap->record[0];
minHeap->record[0] = minHeap->record[minHeap->size - 1];
minHeap->size = minHeap->size - 1;
minHeapify(minHeap, 0);
return temp;
}
void insertMinHeap(struct MinHeap *minHeap, struct TreeNode *minHeapNode)
{
int i = minHeap->size;
minHeap->size = minHeap->size + 1;
while (i != 0 && minHeapNode->freq < minHeap->record[(i - 1) / 2]->freq)
{
minHeap->record[i] = minHeap->record[(i - 1) / 2];
i = (i - 1) / 2;
}
minHeap->record[i] = minHeapNode;
}
void buildMinHeap(struct MinHeap *minHeap)
{
int n = minHeap->size - 1;
for (int i = (n - 1) / 2; i >= 0; --i)
{
minHeapify(minHeap, i);
}
}
struct MinHeap *createAndBuildMinHeap(char element[], int freq[], int size)
{
struct MinHeap *minHeap = createMinHeap(size);
for (int i = 0; i < size; ++i)
{
minHeap->record[i] = newNode(element[i], freq[i]);
}
minHeap->size = size;
buildMinHeap(minHeap);
return minHeap;
}
struct TreeNode *buildHuffmanTree(char element[], int freq[], int size)
{
struct TreeNode *left = NULL;
struct TreeNode *right = NULL;
struct TreeNode *top = NULL;
struct MinHeap *minHeap = createAndBuildMinHeap(element, freq, size);
while (minHeap->size != 1)
{
left = extractMin(minHeap);
right = extractMin(minHeap);
// # indicates internal node
top = newNode('#', left->freq + right->freq);
top->left = left;
top->right = right;
insertMinHeap(minHeap, top);
}
return extractMin(minHeap);
}
// Calculate height of tree
int treeHeight(struct TreeNode *node)
{
if (node != NULL)
{
// Find height of subtree using recursion
int a = treeHeight(node->left);
int b = treeHeight(node->right);
// Returns the height of largest subtree
if (a > b)
{
return a + 1;
}
else
{
return b + 1;
}
}
else
{
return 0;
}
}
void printData(int arr[], int n)
{
for (int i = 0; i < n; ++i)
{
printf("%d", arr[i]);
}
printf("\n");
}
// Find huffman code using recursion
void printCodes(struct TreeNode *root, int record[], int top)
{
if (root->left != NULL)
{
// visit left
record[top] = 0;
printCodes(root->left, record, top + 1);
}
if (root->right != NULL)
{
// visit right
record[top] = 1;
printCodes(root->right, record, top + 1);
}
if (root->left == NULL && root->right == NULL)
{
// When get leaf node
printf("%c : ", root->element);
printData(record, top);
}
}
// Handles the request of printing huffman code
void huffmanCodes(struct TreeNode *root)
{
if (root == NULL)
{
return;
}
// Find height of tree
int height = treeHeight(root);
// This is used to collect human code
int record[height];
// print huffman codes
printCodes(root, record, 0);
}
int main()
{
char element[] = {
'a' , 'b' , 'c' , 'd' , 'e' , 'f' , 'g'
};
int frequency[] = {
16 , 8 , 19 , 32 , 21 , 10 , 5
};
// Get the number of element
int size = sizeof(element) / sizeof(element[0]);
// Create tree
struct HuffmanTree *tree = newTree();
// Construct tree
tree->root = buildHuffmanTree(element, frequency, size);
huffmanCodes(tree->root);
return 0;
}
input
e : 00
f : 010
g : 0110
b : 0111
d : 10
a : 110
c : 111
package main
import "fmt"
/*
Go Program
Ternary Search Tree Insertion
*/
// Tree node
type TreeNode struct {
// Character element
element byte
// Element frequency
freq int
// Left subtree
left * TreeNode
// Right subtree
right * TreeNode
}
func getTreeNode(element byte, freq int) * TreeNode {
var me *TreeNode = &TreeNode {}
me.element = element
me.freq = freq
// Set node child
me.left = nil
me.right = nil
return me
}
// Min heap
type MinHeap struct {
size int
capacity int
// Use to collect record
record [] *TreeNode
}
func getMinHeap(capacity int) * MinHeap {
var me *MinHeap = &MinHeap {}
// Initial number of element
me.size = 0
// Set heap capacity
me.capacity = capacity
// Allocate the memory of record element
me.record = make([]*TreeNode,capacity)
return me
}
// Huffman Tree
type HuffmanTree struct {
root * TreeNode
}
func getHuffmanTree() * HuffmanTree {
var me *HuffmanTree = &HuffmanTree {}
me.root = nil
return me
}
func(this HuffmanTree) minHeapify(minHeap * MinHeap, idx int) {
var smallest int = idx
// Left child
var left int = 2 * idx + 1
// Right child
var right int = 2 * idx + 2
if left < minHeap.size && minHeap.record[left].freq < minHeap.record[smallest].freq {
smallest = left
}
if right < minHeap.size && minHeap.record[right].freq < minHeap.record[smallest].freq {
smallest = right
}
if smallest != idx {
var temp * TreeNode = minHeap.record[smallest]
minHeap.record[smallest] = minHeap.record[idx]
minHeap.record[idx] = temp
this.minHeapify(minHeap, smallest)
}
}
func(this HuffmanTree) extractMin(minHeap * MinHeap) * TreeNode {
var temp * TreeNode = minHeap.record[0]
minHeap.record[0] = minHeap.record[minHeap.size - 1]
minHeap.size = minHeap.size - 1
this.minHeapify(minHeap, 0)
return temp
}
func(this HuffmanTree) insertMinHeap(minHeap * MinHeap, minHeapNode * TreeNode) {
var i int = minHeap.size
minHeap.size = minHeap.size + 1
for (i != 0 && minHeapNode.freq < minHeap.record[(i - 1) / 2].freq) {
minHeap.record[i] = minHeap.record[(i - 1) / 2]
i = (i - 1) / 2
}
minHeap.record[i] = minHeapNode
}
func(this HuffmanTree) buildMinHeap(minHeap * MinHeap) {
var n int = minHeap.size - 1
for i :=(n - 1) / 2 ; i >= 0 ; i-- {
this.minHeapify(minHeap, i)
}
}
func(this HuffmanTree) createAndBuildMinHeap(element[] byte, freq[] int, size int) * MinHeap {
var minHeap * MinHeap = getMinHeap(size)
for i := 0 ; i < size ; i++ {
minHeap.record[i] = getTreeNode(element[i], freq[i])
}
minHeap.size = size
this.buildMinHeap(minHeap)
return minHeap
}
func(this HuffmanTree) buildHuffmanTree(element[] byte, freq[] int, size int) * TreeNode {
var left * TreeNode = nil
var right * TreeNode = nil
var top * TreeNode = nil
var minHeap * MinHeap = this.createAndBuildMinHeap(element, freq, size)
for (minHeap.size != 1) {
left = this.extractMin(minHeap)
right = this.extractMin(minHeap)
// # indicates internal node
top = getTreeNode('#', left.freq + right.freq)
top.left = left
top.right = right
this.insertMinHeap(minHeap, top)
}
return this.extractMin(minHeap)
}
// Calculate height of tree
func(this HuffmanTree) treeHeight(node * TreeNode) int {
if node != nil {
// Find height of subtree using recursion
var a int = this.treeHeight(node.left)
var b int = this.treeHeight(node.right)
// Returns the height of largest subtree
if a > b {
return a + 1
} else {
return b + 1
}
} else {
return 0
}
}
func(this HuffmanTree) printData(arr[] int, n int) {
for i := 0 ; i < n ; i++ {
fmt.Print("", arr[i])
}
fmt.Print("\n")
}
// Find huffman code using recursion
func(this HuffmanTree) printCodes(root * TreeNode, record[] int, top int) {
if root.left != nil {
// visit left
record[top] = 0
this.printCodes(root.left, record, top + 1)
}
if root.right != nil {
// visit right
record[top] = 1
this.printCodes(root.right, record, top + 1)
}
if root.left == nil && root.right == nil {
// When get leaf node
fmt.Printf(" %c : ", root.element)
this.printData(record, top)
}
}
// Handles the request of printing huffman code
func(this HuffmanTree) huffmanCodes() {
if this.root == nil {
return
}
// Find height of tree
var height int = this.treeHeight(this.root)
// This is used to collect human code
var record = make([]int, height)
// print huffman codes
this.printCodes(this.root, record, 0)
}
func main() {
var tree * HuffmanTree = getHuffmanTree()
var element = [] byte {
'a',
'b',
'c',
'd',
'e',
'f',
'g',
}
var frequency = [] int {
16,
8,
19,
32,
21,
10,
5,
}
// Get the number of element
var size int = len(element)
// Construct tree
tree.root = tree.buildHuffmanTree(element, frequency, size)
tree.huffmanCodes()
}
input
e : 00
f : 010
g : 0110
b : 0111
d : 10
a : 110
c : 111
/*
Java Program
Ternary Search Tree Insertion
*/
// Tree node
class TreeNode
{
// Character element
public char element;
// Element frequency
public int freq;
// Left subtree
public TreeNode left;
// Right subtree
public TreeNode right;
public TreeNode(char element, int freq)
{
this.element = element;
this.freq = freq;
// Set node child
this.left = null;
this.right = null;
}
}
// Min heap
class MinHeap
{
public int size;
public int capacity;
// Use to collect record
public TreeNode []record;
public MinHeap(int capacity)
{
// Initial number of element
this.size = 0;
// Set heap capacity
this.capacity = capacity;
// Allocate the memory of record element
this.record = new TreeNode[capacity];
}
}
// Huffman Tree
public class HuffmanTree
{
public TreeNode root;
// Create and return new tree
public HuffmanTree()
{
this.root = null;
}
public void minHeapify(MinHeap minHeap, int idx)
{
int smallest = idx;
// Left child
int left = 2 * idx + 1;
// Right child
int right = 2 * idx + 2;
if (left < minHeap.size
&& minHeap.record[left].freq < minHeap.record[smallest].freq)
{
smallest = left;
}
if (right < minHeap.size
&& minHeap.record[right].freq < minHeap.record[smallest].freq)
{
smallest = right;
}
if (smallest != idx)
{
TreeNode temp = minHeap.record[smallest];
minHeap.record[smallest] = minHeap.record[idx];
minHeap.record[idx] = temp;
minHeapify(minHeap, smallest);
}
}
public TreeNode extractMin(MinHeap minHeap)
{
TreeNode temp = minHeap.record[0];
minHeap.record[0] = minHeap.record[minHeap.size - 1];
minHeap.size = minHeap.size - 1;
minHeapify(minHeap, 0);
return temp;
}
public void insertMinHeap(MinHeap minHeap, TreeNode minHeapNode)
{
int i = minHeap.size;
minHeap.size = minHeap.size + 1;
while (i != 0
&& minHeapNode.freq < minHeap.record[(i - 1) / 2].freq)
{
minHeap.record[i] = minHeap.record[(i - 1) / 2];
i = (i - 1) / 2;
}
minHeap.record[i] = minHeapNode;
}
public void buildMinHeap(MinHeap minHeap)
{
int n = minHeap.size - 1;
for (int i = (n - 1) / 2; i >= 0; --i)
{
minHeapify(minHeap, i);
}
}
public MinHeap createAndBuildMinHeap(char[] element, int[] freq, int size)
{
MinHeap minHeap = new MinHeap(size);
for (int i = 0; i < size; ++i)
{
minHeap.record[i] = new TreeNode(element[i], freq[i]);
}
minHeap.size = size;
buildMinHeap(minHeap);
return minHeap;
}
public TreeNode buildHuffmanTree(char[] element, int[] freq, int size)
{
TreeNode left = null;
TreeNode right = null;
TreeNode top = null;
MinHeap minHeap = createAndBuildMinHeap(element, freq, size);
while (minHeap.size != 1)
{
left = extractMin(minHeap);
right = extractMin(minHeap);
// # indicates internal node
top = new TreeNode('#', left.freq + right.freq);
top.left = left;
top.right = right;
insertMinHeap(minHeap, top);
}
return extractMin(minHeap);
}
// Calculate height of tree
public int treeHeight(TreeNode node)
{
if (node != null)
{
// Find height of subtree using recursion
int a = treeHeight(node.left);
int b = treeHeight(node.right);
// Returns the height of largest subtree
if (a > b)
{
return a + 1;
}
else
{
return b + 1;
}
}
else
{
return 0;
}
}
public void printData(int[] arr, int n)
{
for (int i = 0; i < n; ++i)
{
System.out.print("" + arr[i]);
}
System.out.print("\n");
}
// Find huffman code using recursion
public void printCodes(TreeNode root, int[] record, int top)
{
if (root.left != null)
{
// visit left
record[top] = 0;
printCodes(root.left, record, top + 1);
}
if (root.right != null)
{
// visit right
record[top] = 1;
printCodes(root.right, record, top + 1);
}
if (root.left == null && root.right == null)
{
// When get leaf node
System.out.print(" " + root.element + " : ");
printData(record, top);
}
}
// Handles the request of printing huffman code
public void huffmanCodes()
{
if (this.root == null)
{
return;
}
// Find height of tree
int height = treeHeight(this.root);
// This is used to collect human code
int[] record = new int[height];
// print huffman codes
printCodes(this.root, record, 0);
}
public static void main(String[] args)
{
HuffmanTree tree = new HuffmanTree();
char[] element =
{
'a' , 'b' , 'c' , 'd' , 'e' , 'f' , 'g'
};
int[] frequency =
{
16 , 8 , 19 , 32 , 21 , 10 , 5
};
// Get the number of element
int size = element.length;
// Construct tree
tree.root = tree.buildHuffmanTree(element, frequency, size);
tree.huffmanCodes();
}
}
input
e : 00
f : 010
g : 0110
b : 0111
d : 10
a : 110
c : 111
// Include header file
#include <iostream>
using namespace std;
/*
C++ Program
Ternary Search Tree Insertion
*/
// Tree node
class TreeNode
{
public:
// Character element
char element;
// Element frequency
int freq;
// Left subtree
TreeNode *left;
// Right subtree
TreeNode *right;
TreeNode()
{
this->left = NULL;
this->right = NULL;
}
TreeNode(char element, int freq)
{
this->element = element;
this->freq = freq;
// Set node child
this->left = NULL;
this->right = NULL;
}
};
// Min heap
class MinHeap
{
public:
int size;
int capacity;
// Use to collect record
TreeNode **record;
MinHeap(int capacity)
{
// Initial number of element
this->size = 0;
// Set heap capacity
this->capacity = capacity;
// Allocate the memory of record element
this->record = new TreeNode*[capacity];
}
};
// Huffman Tree
class HuffmanTree
{
public: TreeNode *root;
// Create and return new tree
HuffmanTree()
{
this->root = NULL;
}
void minHeapify(MinHeap *minHeap, int idx)
{
int smallest = idx;
// Left child
int left = 2 *idx + 1;
// Right child
int right = 2 *idx + 2;
if (left < minHeap->size
&& minHeap->record[left]->freq < minHeap->record[smallest]->freq)
{
smallest = left;
}
if (right < minHeap->size
&& minHeap->record[right]->freq < minHeap->record[smallest]->freq)
{
smallest = right;
}
if (smallest != idx)
{
TreeNode *temp = minHeap->record[smallest];
minHeap->record[smallest] = minHeap->record[idx];
minHeap->record[idx] = temp;
this->minHeapify(minHeap, smallest);
}
}
TreeNode *extractMin(MinHeap *minHeap)
{
TreeNode *temp = minHeap->record[0];
minHeap->record[0] = minHeap->record[minHeap->size - 1];
minHeap->size = minHeap->size - 1;
this->minHeapify(minHeap, 0);
return temp;
}
void insertMinHeap(MinHeap *minHeap, TreeNode *minHeapNode)
{
int i = minHeap->size;
minHeap->size = minHeap->size + 1;
while (i != 0
&& minHeapNode->freq < minHeap->record[(i - 1) / 2]->freq)
{
minHeap->record[i] = minHeap->record[(i - 1) / 2];
i = (i - 1) / 2;
}
minHeap->record[i] = minHeapNode;
}
void buildMinHeap(MinHeap *minHeap)
{
int n = minHeap->size - 1;
for (int i = (n - 1) / 2; i >= 0; --i)
{
this->minHeapify(minHeap, i);
}
}
MinHeap *createAndBuildMinHeap(char element[], int freq[], int size)
{
MinHeap *minHeap = new MinHeap(size);
for (int i = 0; i < size; ++i)
{
minHeap->record[i] = new TreeNode(element[i], freq[i]);
}
minHeap->size = size;
this->buildMinHeap(minHeap);
return minHeap;
}
TreeNode *buildHuffmanTree(char element[], int freq[], int size)
{
TreeNode *left = NULL;
TreeNode *right = NULL;
TreeNode *top = NULL;
MinHeap *minHeap = this->createAndBuildMinHeap(element, freq, size);
while (minHeap->size != 1)
{
left = this->extractMin(minHeap);
right = this->extractMin(minHeap);
// # indicates internal node
top = new TreeNode('#', left->freq + right->freq);
top->left = left;
top->right = right;
this->insertMinHeap(minHeap, top);
}
return this->extractMin(minHeap);
}
// Calculate height of tree
int treeHeight(TreeNode *node)
{
if (node != NULL)
{
// Find height of subtree using recursion
int a = this->treeHeight(node->left);
int b = this->treeHeight(node->right);
// Returns the height of largest subtree
if (a > b)
{
return a + 1;
}
else
{
return b + 1;
}
}
else
{
return 0;
}
}
void printData(int arr[], int n)
{
for (int i = 0; i < n; ++i)
{
cout << "" << arr[i];
}
cout << "\n";
}
// Find huffman code using recursion
void printCodes(TreeNode *root, int record[], int top)
{
if (root->left != NULL)
{
// visit left
record[top] = 0;
this->printCodes(root->left, record, top + 1);
}
if (root->right != NULL)
{
// visit right
record[top] = 1;
this->printCodes(root->right, record, top + 1);
}
if (root->left == NULL && root->right == NULL)
{
// When get leaf node
cout << " " << root->element << " : ";
this->printData(record, top);
}
}
// Handles the request of printing huffman code
void huffmanCodes()
{
if (this->root == NULL)
{
return;
}
// Find height of tree
int height = this->treeHeight(this->root);
// This is used to collect human code
int record[height];
// print huffman codes
this->printCodes(this->root, record, 0);
}
};
int main()
{
HuffmanTree *tree = new HuffmanTree();
char element[] = {
'a' , 'b' , 'c' , 'd' , 'e' , 'f' , 'g'
};
int frequency[] = {
16 , 8 , 19 , 32 , 21 , 10 , 5
};
// Get the number of element
int size = sizeof(element) / sizeof(element[0]);
// Construct tree
tree->root = tree->buildHuffmanTree(element, frequency, size);
tree->huffmanCodes();
return 0;
}
input
e : 00
f : 010
g : 0110
b : 0111
d : 10
a : 110
c : 111
// Include namespace system
using System;
/*
Csharp Program
Ternary Search Tree Insertion
*/
// Tree node
public class TreeNode
{
// Character element
public char element;
// Element frequency
public int freq;
// Left subtree
public TreeNode left;
// Right subtree
public TreeNode right;
public TreeNode(char element, int freq)
{
this.element = element;
this.freq = freq;
// Set node child
this.left = null;
this.right = null;
}
}
// Min heap
public class MinHeap
{
public int size;
public int capacity;
// Use to collect record
public TreeNode[] record;
public MinHeap(int capacity)
{
// Initial number of element
this.size = 0;
// Set heap capacity
this.capacity = capacity;
// Allocate the memory of record element
this.record = new TreeNode[capacity];
}
}
// Huffman Tree
public class HuffmanTree
{
public TreeNode root;
// Create and return new tree
public HuffmanTree()
{
this.root = null;
}
public void minHeapify(MinHeap minHeap, int idx)
{
int smallest = idx;
// Left child
int left = 2 * idx + 1;
// Right child
int right = 2 * idx + 2;
if (left < minHeap.size && minHeap.record[left].freq < minHeap.record[smallest].freq)
{
smallest = left;
}
if (right < minHeap.size
&& minHeap.record[right].freq < minHeap.record[smallest].freq)
{
smallest = right;
}
if (smallest != idx)
{
TreeNode temp = minHeap.record[smallest];
minHeap.record[smallest] = minHeap.record[idx];
minHeap.record[idx] = temp;
this.minHeapify(minHeap, smallest);
}
}
public TreeNode extractMin(MinHeap minHeap)
{
TreeNode temp = minHeap.record[0];
minHeap.record[0] = minHeap.record[minHeap.size - 1];
minHeap.size = minHeap.size - 1;
this.minHeapify(minHeap, 0);
return temp;
}
public void insertMinHeap(MinHeap minHeap, TreeNode minHeapNode)
{
int i = minHeap.size;
minHeap.size = minHeap.size + 1;
while (i != 0
&& minHeapNode.freq < minHeap.record[(i - 1) / 2].freq)
{
minHeap.record[i] = minHeap.record[(i - 1) / 2];
i = (i - 1) / 2;
}
minHeap.record[i] = minHeapNode;
}
public void buildMinHeap(MinHeap minHeap)
{
int n = minHeap.size - 1;
for (int i = (n - 1) / 2; i >= 0; --i)
{
this.minHeapify(minHeap, i);
}
}
public MinHeap createAndBuildMinHeap(char[] element, int[] freq, int size)
{
MinHeap minHeap = new MinHeap(size);
for (int i = 0; i < size; ++i)
{
minHeap.record[i] = new TreeNode(element[i], freq[i]);
}
minHeap.size = size;
this.buildMinHeap(minHeap);
return minHeap;
}
public TreeNode buildHuffmanTree(char[] element, int[] freq, int size)
{
TreeNode left = null;
TreeNode right = null;
TreeNode top = null;
MinHeap minHeap = this.createAndBuildMinHeap(element, freq, size);
while (minHeap.size != 1)
{
left = this.extractMin(minHeap);
right = this.extractMin(minHeap);
// # indicates internal node
top = new TreeNode('#', left.freq + right.freq);
top.left = left;
top.right = right;
this.insertMinHeap(minHeap, top);
}
return this.extractMin(minHeap);
}
// Calculate height of tree
public int treeHeight(TreeNode node)
{
if (node != null)
{
// Find height of subtree using recursion
int a = this.treeHeight(node.left);
int b = this.treeHeight(node.right);
// Returns the height of largest subtree
if (a > b)
{
return a + 1;
}
else
{
return b + 1;
}
}
else
{
return 0;
}
}
public void printData(int[] arr, int n)
{
for (int i = 0; i < n; ++i)
{
Console.Write("" + arr[i]);
}
Console.Write("\n");
}
// Find huffman code using recursion
public void printCodes(TreeNode root, int[] record, int top)
{
if (root.left != null)
{
// visit left
record[top] = 0;
this.printCodes(root.left, record, top + 1);
}
if (root.right != null)
{
// visit right
record[top] = 1;
this.printCodes(root.right, record, top + 1);
}
if (root.left == null && root.right == null)
{
// When get leaf node
Console.Write(" " + root.element + " : ");
this.printData(record, top);
}
}
// Handles the request of printing huffman code
public void huffmanCodes()
{
if (this.root == null)
{
return;
}
// Find height of tree
int height = this.treeHeight(this.root);
// This is used to collect human code
int[] record = new int[height];
// print huffman codes
this.printCodes(this.root, record, 0);
}
public static void Main(String[] args)
{
HuffmanTree tree = new HuffmanTree();
char[] element = {
'a' , 'b' , 'c' , 'd' , 'e' , 'f' , 'g'
};
int[] frequency = {
16 , 8 , 19 , 32 , 21 , 10 , 5
};
// Get the number of element
int size = element.Length;
// Construct tree
tree.root = tree.buildHuffmanTree(element, frequency, size);
tree.huffmanCodes();
}
}
input
e : 00
f : 010
g : 0110
b : 0111
d : 10
a : 110
c : 111
<?php
/*
Php Program
Ternary Search Tree Insertion
*/
// Tree node
class TreeNode
{
// Character element
public $element;
// Element frequency
public $freq;
// Left subtree
public $left;
// Right subtree
public $right;
public function __construct($element, $freq)
{
$this->element = $element;
$this->freq = $freq;
// Set node child
$this->left = NULL;
$this->right = NULL;
}
}
// Min heap
class MinHeap
{
public $size;
public $capacity;
// Use to collect record
public $record;
public function __construct($capacity)
{
// Initial number of element
$this->size = 0;
// Set heap capacity
$this->capacity = $capacity;
// Allocate the memory of record element
$this->record = array_fill(0, $capacity, NULL);
}
}
// Huffman Tree
class HuffmanTree
{
public $root;
// Create and return new tree
public function __construct()
{
$this->root = NULL;
}
public function minHeapify($minHeap, $idx)
{
$smallest = $idx;
// Left child
$left = 2 * $idx + 1;
// Right child
$right = 2 * $idx + 2;
if ($left < $minHeap->size
&& $minHeap->record[$left]->freq
< $minHeap->record[$smallest]->freq)
{
$smallest = $left;
}
if ($right < $minHeap->size
&& $minHeap->record[$right]->freq
< $minHeap->record[$smallest]->freq)
{
$smallest = $right;
}
if ($smallest != $idx)
{
$temp = $minHeap->record[$smallest];
$minHeap->record[$smallest] = $minHeap->record[$idx];
$minHeap->record[$idx] = $temp;
$this->minHeapify($minHeap, $smallest);
}
}
public function extractMin($minHeap)
{
$temp = $minHeap->record[0];
$minHeap->record[0] = $minHeap->record[$minHeap->size - 1];
$minHeap->size = $minHeap->size - 1;
$this->minHeapify($minHeap, 0);
return $temp;
}
public function insertMinHeap($minHeap, $minHeapNode)
{
$i = $minHeap->size;
$minHeap->size = $minHeap->size + 1;
while ($i != 0
&& $minHeapNode->freq
< $minHeap->record[(int)(($i - 1) / 2)]->freq)
{
$minHeap->record[$i] = $minHeap->record[(int)(($i - 1) / 2)];
$i = (int)(($i - 1) / 2);
}
$minHeap->record[$i] = $minHeapNode;
}
public function buildMinHeap($minHeap)
{
$n = $minHeap->size - 1;
for ($i = (int)(($n - 1) / 2); $i >= 0; --$i)
{
$this->minHeapify($minHeap, $i);
}
}
public function createAndBuildMinHeap($element, $freq, $size)
{
$minHeap = new MinHeap($size);
for ($i = 0; $i < $size; ++$i)
{
$minHeap->record[$i] = new TreeNode($element[$i], $freq[$i]);
}
$minHeap->size = $size;
$this->buildMinHeap($minHeap);
return $minHeap;
}
public function buildHuffmanTree($element, $freq, $size)
{
$left = NULL;
$right = NULL;
$top = NULL;
$minHeap = $this->createAndBuildMinHeap($element, $freq, $size);
while ($minHeap->size != 1)
{
$left = $this->extractMin($minHeap);
$right = $this->extractMin($minHeap);
// # indicates internal node
$top = new TreeNode('#', $left->freq + $right->freq);
$top->left = $left;
$top->right = $right;
$this->insertMinHeap($minHeap, $top);
}
return $this->extractMin($minHeap);
}
// Calculate height of tree
public function treeHeight($node)
{
if ($node != NULL)
{
// Find height of subtree using recursion
$a = $this->treeHeight($node->left);
$b = $this->treeHeight($node->right);
// Returns the height of largest subtree
if ($a > $b)
{
return $a + 1;
}
else
{
return $b + 1;
}
}
else
{
return 0;
}
}
public function printData($arr, $n)
{
for ($i = 0; $i < $n; ++$i)
{
echo("".$arr[$i]);
}
echo("\n");
}
// Find huffman code using recursion
public function printCodes($root, $record, $top)
{
if ($root->left != NULL)
{
// visit left
$record[$top] = 0;
$this->printCodes($root->left, $record, $top + 1);
}
if ($root->right != NULL)
{
// visit right
$record[$top] = 1;
$this->printCodes($root->right, $record, $top + 1);
}
if ($root->left == NULL && $root->right == NULL)
{
// When get leaf node
echo(" ".$root->element.
" : ");
$this->printData($record, $top);
}
}
// Handles the request of printing huffman code
public function huffmanCodes()
{
if ($this->root == NULL)
{
return;
}
// Find height of tree
$height = $this->treeHeight($this->root);
// This is used to collect human code
$record = array_fill(0, $height, 0);
// print huffman codes
$this->printCodes($this->root, $record, 0);
}
}
function main()
{
$tree = new HuffmanTree();
$element = array('a', 'b', 'c', 'd', 'e', 'f', 'g');
$frequency = array(16, 8, 19, 32, 21, 10, 5);
// Get the number of element
$size = count($element);
// Construct tree
$tree->root = $tree->buildHuffmanTree($element, $frequency, $size);
$tree->huffmanCodes();
}
main();
input
e : 00
f : 010
g : 0110
b : 0111
d : 10
a : 110
c : 111
/*
Node JS Program
Ternary Search Tree Insertion
*/
// Tree node
class TreeNode
{
constructor(element, freq)
{
this.element = element;
this.freq = freq;
// Set node child
this.left = null;
this.right = null;
}
}
// Min heap
class MinHeap
{
constructor(capacity)
{
// Initial number of element
this.size = 0;
// Set heap capacity
this.capacity = capacity;
// Allocate the memory of record element
this.record = Array(capacity).fill(null);
}
}
// Huffman Tree
class HuffmanTree
{
// Create and return new tree
constructor()
{
this.root = null;
}
minHeapify(minHeap, idx)
{
var smallest = idx;
// Left child
var left = 2 * idx + 1;
// Right child
var right = 2 * idx + 2;
if (left < minHeap.size
&& minHeap.record[left].freq
< minHeap.record[smallest].freq)
{
smallest = left;
}
if (right < minHeap.size
&& minHeap.record[right].freq
< minHeap.record[smallest].freq)
{
smallest = right;
}
if (smallest != idx)
{
var temp = minHeap.record[smallest];
minHeap.record[smallest] = minHeap.record[idx];
minHeap.record[idx] = temp;
this.minHeapify(minHeap, smallest);
}
}
extractMin(minHeap)
{
var temp = minHeap.record[0];
minHeap.record[0] = minHeap.record[minHeap.size - 1];
minHeap.size = minHeap.size - 1;
this.minHeapify(minHeap, 0);
return temp;
}
insertMinHeap(minHeap, minHeapNode)
{
var i = minHeap.size;
minHeap.size = minHeap.size + 1;
while (i != 0
&& minHeapNode.freq
< minHeap.record[parseInt((i - 1) / 2)].freq)
{
minHeap.record[i] = minHeap.record[parseInt((i - 1) / 2)];
i = parseInt((i - 1) / 2);
}
minHeap.record[i] = minHeapNode;
}
buildMinHeap(minHeap)
{
var n = minHeap.size - 1;
for (var i = parseInt((n - 1) / 2); i >= 0; --i)
{
this.minHeapify(minHeap, i);
}
}
createAndBuildMinHeap(element, freq, size)
{
var minHeap = new MinHeap(size);
for (var i = 0; i < size; ++i)
{
minHeap.record[i] = new TreeNode(element[i], freq[i]);
}
minHeap.size = size;
this.buildMinHeap(minHeap);
return minHeap;
}
buildHuffmanTree(element, freq, size)
{
var left = null;
var right = null;
var top = null;
var minHeap = this.createAndBuildMinHeap(element, freq, size);
while (minHeap.size != 1)
{
left = this.extractMin(minHeap);
right = this.extractMin(minHeap);
// # indicates internal node
top = new TreeNode('#', left.freq + right.freq);
top.left = left;
top.right = right;
this.insertMinHeap(minHeap, top);
}
return this.extractMin(minHeap);
}
// Calculate height of tree
treeHeight(node)
{
if (node != null)
{
// Find height of subtree using recursion
var a = this.treeHeight(node.left);
var b = this.treeHeight(node.right);
// Returns the height of largest subtree
if (a > b)
{
return a + 1;
}
else
{
return b + 1;
}
}
else
{
return 0;
}
}
printData(arr, n)
{
for (var i = 0; i < n; ++i)
{
process.stdout.write("" + arr[i]);
}
process.stdout.write("\n");
}
// Find huffman code using recursion
printCodes(root, record, top)
{
if (root.left != null)
{
// visit left
record[top] = 0;
this.printCodes(root.left, record, top + 1);
}
if (root.right != null)
{
// visit right
record[top] = 1;
this.printCodes(root.right, record, top + 1);
}
if (root.left == null && root.right == null)
{
// When get leaf node
process.stdout.write(" " + root.element + " : ");
this.printData(record, top);
}
}
// Handles the request of printing huffman code
huffmanCodes()
{
if (this.root == null)
{
return;
}
// Find height of tree
var height = this.treeHeight(this.root);
// This is used to collect human code
var record = Array(height).fill(0);
// print huffman codes
this.printCodes(this.root, record, 0);
}
}
function main()
{
var tree = new HuffmanTree();
var element = ['a', 'b', 'c', 'd', 'e', 'f', 'g'];
var frequency = [16, 8, 19, 32, 21, 10, 5];
// Get the number of element
var size = element.length;
// Construct tree
tree.root = tree.buildHuffmanTree(element, frequency, size);
tree.huffmanCodes();
}
main();
input
e : 00
f : 010
g : 0110
b : 0111
d : 10
a : 110
c : 111
# Python 3 Program
# Ternary Search Tree Insertion
# Tree node
class TreeNode :
# Character element
# Element frequency
# Left subtree
# Right subtree
def __init__(self, element, freq) :
self.element = element
self.freq = freq
# Set node child
self.left = None
self.right = None
# Min heap
class MinHeap :
# Use to collect record
def __init__(self, capacity) :
# Initial number of element
self.size = 0
# Set heap capacity
self.capacity = capacity
# Allocate the memory of record element
self.record = [None] * (capacity)
# Huffman Tree
class HuffmanTree :
# Create and return new tree
def __init__(self) :
self.root = None
def minHeapify(self, minHeap, idx) :
smallest = idx
# Left child
left = 2 * idx + 1
# Right child
right = 2 * idx + 2
if (left < minHeap.size and
minHeap.record[left].freq < minHeap.record[smallest].freq) :
smallest = left
if (right < minHeap.size and
minHeap.record[right].freq < minHeap.record[smallest].freq) :
smallest = right
if (smallest != idx) :
temp = minHeap.record[smallest]
minHeap.record[smallest] = minHeap.record[idx]
minHeap.record[idx] = temp
self.minHeapify(minHeap, smallest)
def extractMin(self, minHeap) :
temp = minHeap.record[0]
minHeap.record[0] = minHeap.record[minHeap.size - 1]
minHeap.size = minHeap.size - 1
self.minHeapify(minHeap, 0)
return temp
def insertMinHeap(self, minHeap, minHeapNode) :
i = minHeap.size
minHeap.size = minHeap.size + 1
while (i != 0 and
minHeapNode.freq < minHeap.record[int((i - 1) / 2)].freq) :
minHeap.record[i] = minHeap.record[int((i - 1) / 2)]
i = int((i - 1) / 2)
minHeap.record[i] = minHeapNode
def buildMinHeap(self, minHeap) :
n = minHeap.size - 1
i = int((n - 1) / 2)
while (i >= 0) :
self.minHeapify(minHeap, i)
i -= 1
def createAndBuildMinHeap(self, element, freq, size) :
minHeap = MinHeap(size)
i = 0
while (i < size) :
minHeap.record[i] = TreeNode(element[i], freq[i])
i += 1
minHeap.size = size
self.buildMinHeap(minHeap)
return minHeap
def buildHuffmanTree(self, element, freq, size) :
left = None
right = None
top = None
minHeap = self.createAndBuildMinHeap(element, freq, size)
while (minHeap.size != 1) :
left = self.extractMin(minHeap)
right = self.extractMin(minHeap)
# # indicates internal node
top = TreeNode('#', left.freq + right.freq)
top.left = left
top.right = right
self.insertMinHeap(minHeap, top)
return self.extractMin(minHeap)
# Calculate height of tree
def treeHeight(self, node) :
if (node != None) :
# Find height of subtree using recursion
a = self.treeHeight(node.left)
b = self.treeHeight(node.right)
# Returns the height of largest subtree
if (a > b) :
return a + 1
else :
return b + 1
else :
return 0
def printData(self, arr, n) :
i = 0
while (i < n) :
print("", arr[i], end = "")
i += 1
print(end = "\n")
# Find huffman code using recursion
def printCodes(self, root, record, top) :
if (root.left != None) :
# visit left
record[top] = 0
self.printCodes(root.left, record, top + 1)
if (root.right != None) :
# visit right
record[top] = 1
self.printCodes(root.right, record, top + 1)
if (root.left == None and root.right == None) :
# When get leaf node
print(" ", root.element ," : ", end = "")
self.printData(record, top)
# Handles the request of printing huffman code
def huffmanCodes(self) :
if (self.root == None) :
return
# Find height of tree
height = self.treeHeight(self.root)
# This is used to collect human code
record = [0] * (height)
# print huffman codes
self.printCodes(self.root, record, 0)
def main() :
tree = HuffmanTree()
element = ['a', 'b', 'c', 'd', 'e', 'f', 'g']
frequency = [16, 8, 19, 32, 21, 10, 5]
# Get the number of element
size = len(element)
# Construct tree
tree.root = tree.buildHuffmanTree(element, frequency, size)
tree.huffmanCodes()
if __name__ == "__main__": main()
input
e : 0 0
f : 0 1 0
g : 0 1 1 0
b : 0 1 1 1
d : 1 0
a : 1 1 0
c : 1 1 1
# Ruby Program
# Ternary Search Tree Insertion
# Tree node
class TreeNode
# Define the accessor and reader of class TreeNode
attr_reader :element, :freq, :left, :right
attr_accessor :element, :freq, :left, :right
# Character element
# Element frequency
# Left subtree
# Right subtree
def initialize(element, freq)
self.element = element
self.freq = freq
# Set node child
self.left = nil
self.right = nil
end
end
# Min heap
class MinHeap
# Define the accessor and reader of class MinHeap
attr_reader :size, :capacity, :record
attr_accessor :size, :capacity, :record
# Use to collect record
def initialize(capacity)
# Initial number of element
self.size = 0
# Set heap capacity
self.capacity = capacity
# Allocate the memory of record element
self.record = Array.new(capacity) {nil}
end
end
# Huffman Tree
class HuffmanTree
# Define the accessor and reader of class HuffmanTree
attr_reader :root
attr_accessor :root
# Create and return new tree
def initialize()
self.root = nil
end
def minHeapify(minHeap, idx)
smallest = idx
# Left child
left = 2 * idx + 1
# Right child
right = 2 * idx + 2
if (left < minHeap.size &&
minHeap.record[left].freq < minHeap.record[smallest].freq)
smallest = left
end
if (right < minHeap.size &&
minHeap.record[right].freq < minHeap.record[smallest].freq)
smallest = right
end
if (smallest != idx)
temp = minHeap.record[smallest]
minHeap.record[smallest] = minHeap.record[idx]
minHeap.record[idx] = temp
self.minHeapify(minHeap, smallest)
end
end
def extractMin(minHeap)
temp = minHeap.record[0]
minHeap.record[0] = minHeap.record[minHeap.size - 1]
minHeap.size = minHeap.size - 1
self.minHeapify(minHeap, 0)
return temp
end
def insertMinHeap(minHeap, minHeapNode)
i = minHeap.size
minHeap.size = minHeap.size + 1
while (i != 0 && minHeapNode.freq < minHeap.record[(i - 1) / 2].freq)
minHeap.record[i] = minHeap.record[(i - 1) / 2]
i = (i - 1) / 2
end
minHeap.record[i] = minHeapNode
end
def buildMinHeap(minHeap)
n = minHeap.size - 1
i = (n - 1) / 2
while (i >= 0)
self.minHeapify(minHeap, i)
i -= 1
end
end
def createAndBuildMinHeap(element, freq, size)
minHeap = MinHeap.new(size)
i = 0
while (i < size)
minHeap.record[i] = TreeNode.new(element[i], freq[i])
i += 1
end
minHeap.size = size
self.buildMinHeap(minHeap)
return minHeap
end
def buildHuffmanTree(element, freq, size)
left = nil
right = nil
top = nil
minHeap = self.createAndBuildMinHeap(element, freq, size)
while (minHeap.size != 1)
left = self.extractMin(minHeap)
right = self.extractMin(minHeap)
# # indicates internal node
top = TreeNode.new('#', left.freq + right.freq)
top.left = left
top.right = right
self.insertMinHeap(minHeap, top)
end
return self.extractMin(minHeap)
end
# Calculate height of tree
def treeHeight(node)
if (node != nil)
# Find height of subtree using recursion
a = self.treeHeight(node.left)
b = self.treeHeight(node.right)
# Returns the height of largest subtree
if (a > b)
return a + 1
else
return b + 1
end
else
return 0
end
end
def printData(arr, n)
i = 0
while (i < n)
print("", arr[i])
i += 1
end
print("\n")
end
# Find huffman code using recursion
def printCodes(root, record, top)
if (root.left != nil)
# visit left
record[top] = 0
self.printCodes(root.left, record, top + 1)
end
if (root.right != nil)
# visit right
record[top] = 1
self.printCodes(root.right, record, top + 1)
end
if (root.left == nil && root.right == nil)
# When get leaf node
print(" ", root.element ," : ")
self.printData(record, top)
end
end
# Handles the request of printing huffman code
def huffmanCodes()
if (self.root == nil)
return
end
# Find height of tree
height = self.treeHeight(self.root)
# This is used to collect human code
record = Array.new(height) {0}
# print huffman codes
self.printCodes(self.root, record, 0)
end
end
def main()
tree = HuffmanTree.new()
element = ['a', 'b', 'c', 'd', 'e', 'f', 'g']
frequency = [16, 8, 19, 32, 21, 10, 5]
# Get the number of element
size = element.length
# Construct tree
tree.root = tree.buildHuffmanTree(element, frequency, size)
tree.huffmanCodes()
end
main()
input
e : 00
f : 010
g : 0110
b : 0111
d : 10
a : 110
c : 111
/*
Scala Program
Ternary Search Tree Insertion
*/
// Tree node
class TreeNode(
// Character element
var element: Char,
// Element frequency
var freq: Int,
// Left subtree
var left: TreeNode,
// Right subtree
var right: TreeNode)
{
def this(element: Char, freq: Int)
{
this(element,freq,null,null);
}
}
// Min heap
class MinHeap(var size: Int,
var capacity: Int,
// Use to collect record
var record: Array[TreeNode])
{
def this(capacity: Int)
{
// Initial number of element
this(0, capacity,Array.fill[TreeNode](capacity)(null));
}
}
// Huffman Tree
class HuffmanTree(var root: TreeNode)
{
// Create and return new tree
def this()
{
this(null);
}
def minHeapify(minHeap: MinHeap, idx: Int): Unit = {
var smallest: Int = idx;
// Left child
var left: Int = 2 * idx + 1;
// Right child
var right: Int = 2 * idx + 2;
if (left < minHeap.size &&
minHeap.record(left).freq < minHeap.record(smallest).freq)
{
smallest = left;
}
if (right < minHeap.size &&
minHeap.record(right).freq < minHeap.record(smallest).freq)
{
smallest = right;
}
if (smallest != idx)
{
var temp: TreeNode = minHeap.record(smallest);
minHeap.record(smallest) = minHeap.record(idx);
minHeap.record(idx) = temp;
minHeapify(minHeap, smallest);
}
}
def extractMin(minHeap: MinHeap): TreeNode = {
var temp: TreeNode = minHeap.record(0);
minHeap.record(0) = minHeap.record(minHeap.size - 1);
minHeap.size = minHeap.size - 1;
minHeapify(minHeap, 0);
return temp;
}
def insertMinHeap(minHeap: MinHeap, minHeapNode: TreeNode): Unit = {
var i: Int = minHeap.size;
minHeap.size = minHeap.size + 1;
while (i != 0
&& minHeapNode.freq < minHeap.record((i - 1) / 2).freq)
{
minHeap.record(i) = minHeap.record((i - 1) / 2);
i = (i - 1) / 2;
}
minHeap.record(i) = minHeapNode;
}
def buildMinHeap(minHeap: MinHeap): Unit = {
var n: Int = minHeap.size - 1;
var i: Int = (n - 1) / 2;
while (i >= 0)
{
minHeapify(minHeap, i);
i -= 1;
}
}
def createAndBuildMinHeap(
element: Array[Char],
freq: Array[Int],
size: Int):
MinHeap = {
var minHeap: MinHeap = new MinHeap(size);
var i: Int = 0;
while (i < size)
{
minHeap.record(i) = new TreeNode(element(i), freq(i));
i += 1;
}
minHeap.size = size;
buildMinHeap(minHeap);
return minHeap;
}
def buildHuffmanTree(
element: Array[Char],
freq: Array[Int],
size: Int): TreeNode = {
var left: TreeNode = null;
var right: TreeNode = null;
var top: TreeNode = null;
var minHeap: MinHeap = createAndBuildMinHeap(element, freq, size);
while (minHeap.size != 1)
{
left = extractMin(minHeap);
right = extractMin(minHeap);
// # indicates internal node
top = new TreeNode('#', left.freq + right.freq);
top.left = left;
top.right = right;
insertMinHeap(minHeap, top);
}
return extractMin(minHeap);
}
// Calculate height of tree
def treeHeight(node: TreeNode): Int = {
if (node != null)
{
// Find height of subtree using recursion
var a: Int = treeHeight(node.left);
var b: Int = treeHeight(node.right);
// Returns the height of largest subtree
if (a > b)
{
return a + 1;
}
else
{
return b + 1;
}
}
else
{
return 0;
}
}
def printData(arr: Array[Int], n: Int): Unit = {
var i: Int = 0;
while (i < n)
{
print("" + arr(i));
i += 1;
}
print("\n");
}
// Find huffman code using recursion
def printCodes(root: TreeNode, record: Array[Int], top: Int): Unit = {
if (root.left != null)
{
// visit left
record(top) = 0;
printCodes(root.left, record, top + 1);
}
if (root.right != null)
{
// visit right
record(top) = 1;
printCodes(root.right, record, top + 1);
}
if (root.left == null && root.right == null)
{
// When get leaf node
print(" " + root.element + " : ");
printData(record, top);
}
}
// Handles the request of printing huffman code
def huffmanCodes(): Unit = {
if (this.root == null)
{
return;
}
// Find height of tree
var height: Int = treeHeight(this.root);
// This is used to collect human code
var record: Array[Int] = Array.fill[Int](height)(0);
// print huffman codes
printCodes(this.root, record, 0);
}
}
object Main
{
def main(args: Array[String]): Unit = {
var tree: HuffmanTree = new HuffmanTree();
var element: Array[Char] = Array('a', 'b', 'c', 'd', 'e', 'f', 'g');
var frequency: Array[Int] = Array(16, 8, 19, 32, 21, 10, 5);
// Get the number of element
var size: Int = element.length;
// Construct tree
tree.root = tree.buildHuffmanTree(element, frequency, size);
tree.huffmanCodes();
}
}
input
e : 00
f : 010
g : 0110
b : 0111
d : 10
a : 110
c : 111
import Foundation;
/*
Swift 4 Program
Ternary Search Tree Insertion
*/
// Tree node
class TreeNode
{
// Character element
var element: Character;
// Element frequency
var freq: Int;
// Left subtree
var left: TreeNode? ;
// Right subtree
var right: TreeNode? ;
init(_ element: Character, _ freq: Int)
{
self.element = element;
self.freq = freq;
// Set node child
self.left = nil;
self.right = nil;
}
}
// Min heap
class MinHeap
{
var size: Int;
var capacity: Int;
// Use to collect record
var record: [TreeNode? ];
init(_ capacity: Int)
{
// Initial number of element
self.size = 0;
// Set heap capacity
self.capacity = capacity;
// Allocate the memory of record element
self.record = Array(repeating: nil, count: capacity);
}
}
// Huffman Tree
class HuffmanTree
{
var root: TreeNode? ;
// Create and return new tree
init()
{
self.root = nil;
}
func minHeapify(_ minHeap: MinHeap? , _ idx : Int)
{
var smallest = idx;
// Left child
let left = 2 * idx + 1;
// Right child
let right = 2 * idx + 2;
if (left < minHeap!.size
&& minHeap!.record[left]!.freq < minHeap!.record[smallest]!.freq)
{
smallest = left;
}
if (right < minHeap!.size && minHeap!.record[right]!.freq < minHeap!.record[smallest]!.freq)
{
smallest = right;
}
if (smallest != idx)
{
let temp = minHeap!.record[smallest];
minHeap!.record[smallest] = minHeap!.record[idx];
minHeap!.record[idx] = temp;
self.minHeapify(minHeap, smallest);
}
}
func extractMin(_ minHeap: MinHeap? ) -> TreeNode?
{
let temp = minHeap!.record[0];
minHeap!.record[0] = minHeap!.record[minHeap!.size - 1];
minHeap!.size = minHeap!.size - 1;
self.minHeapify(minHeap, 0);
return temp;
}
func insertMinHeap(_ minHeap: MinHeap? , _ minHeapNode : TreeNode? )
{
var i = minHeap!.size;
minHeap!.size = minHeap!.size + 1;
while (i != 0 && minHeapNode!.freq < minHeap!.record[(i - 1) / 2]!.freq)
{
minHeap!.record[i] = minHeap!.record[(i - 1) / 2];
i = (i - 1) / 2;
}
minHeap!.record[i] = minHeapNode;
}
func buildMinHeap(_ minHeap: MinHeap? )
{
let n = minHeap!.size - 1;
var i = (n - 1) / 2;
while (i >= 0)
{
self.minHeapify(minHeap, i);
i -= 1;
}
}
func createAndBuildMinHeap(_ element: [Character], _ freq: [Int], _ size: Int) -> MinHeap?
{
let minHeap = MinHeap(size);
var i = 0;
while (i < size)
{
minHeap.record[i] = TreeNode(element[i], freq[i]);
i += 1;
}
minHeap.size = size;
self.buildMinHeap(minHeap);
return minHeap;
}
func buildHuffmanTree(_ element: [Character], _ freq: [Int], _ size: Int) -> TreeNode?
{
var left :TreeNode? = nil;
var right :TreeNode? = nil;
var top :TreeNode? = nil;
let minHeap = self.createAndBuildMinHeap(element, freq, size);
while (minHeap!.size != 1)
{
left = self.extractMin(minHeap);
right = self.extractMin(minHeap);
// # indicates internal node
top = TreeNode("#", left!.freq + right!.freq);
top!.left = left;
top!.right = right;
self.insertMinHeap(minHeap, top);
}
return self.extractMin(minHeap);
}
// Calculate height of tree
func treeHeight(_ node: TreeNode? ) -> Int
{
if (node != nil)
{
// Find height of subtree using recursion
let a = self.treeHeight(node!.left);
let b = self.treeHeight(node!.right);
// Returns the height of largest subtree
if (a > b)
{
return a + 1;
}
else
{
return b + 1;
}
}
else
{
return 0;
}
}
func printData(_ arr: [Int], _ n: Int)
{
var i = 0;
while (i < n)
{
print("", arr[i], terminator: "");
i += 1;
}
print(terminator: "\n");
}
// Find huffman code using recursion
func printCodes(_ root: TreeNode? , _ record : inout[Int], _ top: Int)
{
if (root!.left != nil)
{
// visit left
record[top] = 0;
self.printCodes(root!.left, &record, top + 1);
}
if (root!.right != nil)
{
// visit right
record[top] = 1;
self.printCodes(root!.right, &record, top + 1);
}
if (root!.left == nil && root!.right == nil)
{
// When get leaf node
print(" ", root!.element ," : ", terminator: "");
self.printData(record, top);
}
}
// Handles the request of printing huffman code
func huffmanCodes()
{
if (self.root == nil)
{
return;
}
// Find height of tree
let height = self.treeHeight(self.root);
// This is used to collect human code
var record = Array(repeating: 0, count: height);
// print huffman codes
self.printCodes(self.root, &record, 0);
}
}
func main()
{
let tree = HuffmanTree();
let element : [Character] = ["a", "b", "c", "d", "e", "f", "g"];
let frequency : [Int] = [16, 8, 19, 32, 21, 10, 5];
// Get the number of element
let size = element.count;
// Construct tree
tree.root = tree.buildHuffmanTree(element, frequency, size);
tree.huffmanCodes();
}
main();
input
e : 0 0
f : 0 1 0
g : 0 1 1 0
b : 0 1 1 1
d : 1 0
a : 1 1 0
c : 1 1 1
/*
Kotlin Program
Ternary Search Tree Insertion
*/
// Tree node
class TreeNode
{
// Character element
var element: Char;
// Element frequency
var freq: Int;
// Left subtree
var left: TreeNode ? ;
// Right subtree
var right: TreeNode ? ;
constructor(element: Char, freq: Int)
{
this.element = element;
this.freq = freq;
// Set node child
this.left = null;
this.right = null;
}
}
// Min heap
class MinHeap
{
var size: Int;
var capacity: Int;
// Use to collect record
var record: Array < TreeNode ? > ;
constructor(capacity: Int)
{
// Initial number of element
this.size = 0;
// Set heap capacity
this.capacity = capacity;
// Allocate the memory of record element
this.record = Array(capacity)
{
null
};
}
}
// Huffman Tree
class HuffmanTree
{
var root: TreeNode ? ;
// Create and return new tree
constructor()
{
this.root = null;
}
fun minHeapify(minHeap: MinHeap ? , idx : Int): Unit
{
var smallest: Int = idx;
// Left child
var left: Int = 2 * idx + 1;
// Right child
var right: Int = 2 * idx + 2;
if (left < minHeap!!.size &&
minHeap.record[left]!!.freq < minHeap.record[smallest]!!.freq)
{
smallest = left;
}
if (right < minHeap.size && minHeap.record[right]!!.freq < minHeap.record[smallest]!!.freq)
{
smallest = right;
}
if (smallest != idx)
{
val temp: TreeNode? = minHeap.record[smallest];
minHeap.record[smallest] = minHeap.record[idx];
minHeap.record[idx] = temp;
this.minHeapify(minHeap, smallest);
}
}
fun extractMin(minHeap: MinHeap ? ): TreeNode ?
{
val temp: TreeNode? = minHeap!!.record[0];
minHeap.record[0] = minHeap.record[minHeap.size - 1];
minHeap.size = minHeap.size - 1;
this.minHeapify(minHeap, 0);
return temp;
}
fun insertMinHeap(minHeap: MinHeap ? , minHeapNode : TreeNode ? ): Unit
{
var i: Int = minHeap!!.size;
minHeap.size = minHeap.size + 1;
while (i != 0 &&
minHeapNode!!.freq < minHeap.record[(i - 1) / 2]!!.freq)
{
minHeap.record[i] = minHeap.record[(i - 1) / 2];
i = (i - 1) / 2;
}
minHeap.record[i] = minHeapNode;
}
fun buildMinHeap(minHeap: MinHeap ? ): Unit
{
val n: Int = minHeap!!.size - 1;
var i: Int = (n - 1) / 2;
while (i >= 0)
{
this.minHeapify(minHeap, i);
i -= 1;
}
}
fun createAndBuildMinHeap(element: Array < Char > , freq: Array < Int > , size: Int): MinHeap ?
{
val minHeap: MinHeap = MinHeap(size);
var i: Int = 0;
while (i < size)
{
minHeap.record[i] = TreeNode(element[i], freq[i]);
i += 1;
}
minHeap.size = size;
this.buildMinHeap(minHeap);
return minHeap;
}
fun buildHuffmanTree(element: Array < Char > , freq: Array < Int > , size: Int): TreeNode ?
{
var left: TreeNode ? ;
var right: TreeNode ? ;
var top: TreeNode ? ;
val minHeap: MinHeap? = this.createAndBuildMinHeap(element, freq, size);
while (minHeap!!.size != 1)
{
left = this.extractMin(minHeap);
right = this.extractMin(minHeap);
// # indicates internal node
top = TreeNode('#', left!!.freq + right!!.freq);
top.left = left;
top.right = right;
this.insertMinHeap(minHeap, top);
}
return this.extractMin(minHeap);
}
// Calculate height of tree
fun treeHeight(node: TreeNode ? ): Int
{
if (node != null)
{
// Find height of subtree using recursion
val a: Int = this.treeHeight(node.left);
val b: Int = this.treeHeight(node.right);
// Returns the height of largest subtree
if (a > b)
{
return a + 1;
}
else
{
return b + 1;
}
}
else
{
return 0;
}
}
fun printData(arr: Array < Int > , n: Int): Unit
{
var i: Int = 0;
while (i < n)
{
print("" + arr[i]);
i += 1;
}
print("\n");
}
// Find huffman code using recursion
fun printCodes(root: TreeNode ? , record : Array < Int > , top: Int): Unit
{
if (root!!.left != null)
{
// visit left
record[top] = 0;
this.printCodes(root.left, record, top + 1);
}
if (root.right != null)
{
// visit right
record[top] = 1;
this.printCodes(root.right, record, top + 1);
}
if (root.left == null && root.right == null)
{
// When get leaf node
print(" " + root.element + " : ");
this.printData(record, top);
}
}
// Handles the request of printing huffman code
fun huffmanCodes(): Unit
{
if (this.root == null)
{
return;
}
// Find height of tree
val height: Int = this.treeHeight(this.root);
// This is used to collect human code
val record: Array < Int > = Array(height)
{
0
};
// print huffman codes
this.printCodes(this.root, record, 0);
}
}
fun main(args: Array < String > ): Unit
{
val tree: HuffmanTree = HuffmanTree();
val element: Array < Char > = arrayOf('a', 'b', 'c', 'd', 'e', 'f', 'g');
val frequency: Array < Int > = arrayOf(16, 8, 19, 32, 21, 10, 5);
// Get the number of element
val size: Int = element.count();
// Construct tree
tree.root = tree.buildHuffmanTree(element, frequency, size);
tree.huffmanCodes();
}
input
e : 00
f : 010
g : 0110
b : 0111
d : 10
a : 110
c : 111
Time Complexity
- Creating and building the min heap takes O(n) time.
- Constructing the Huffman Tree involves n-1 iterations of extracting and inserting nodes from and to the min heap, each operation takes O(log n) time.
- Generating Huffman codes by traversing the tree also takes O(n) time.
- Overall, the time complexity of the algorithm is O(n log n).
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