Skip to main content

Huffman Tree Example

Here given code implementation process.

// 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




Comment

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

New Comment