Skip to main content

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

  1. Create a priority queue (min heap) of characters along with their frequencies.
  2. 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.
  3. The remaining node in the queue is the root of the Huffman Tree.

Algorithm Explanation

  1. Create a min heap to store nodes along with their frequencies.
  2. For each character and its frequency, create a tree node and insert it into the min heap.
  3. 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.
  4. The last remaining node in the min heap is the root of the Huffman Tree.
  5. 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.
  6. 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

  1. Creating and building the min heap takes O(n) time.
  2. 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.
  3. Generating Huffman codes by traversing the tree also takes O(n) time.
  4. Overall, the time complexity of the algorithm is O(n log n).
Last updated on by Kalkicode




Comment

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

New Comment