Efficient Huffman Coding for Sorted Input | Greedy Algo | C ++ Program for Efficient Huffman Coding for Sorted input ; This constant can be avoided by explicitly calculating height of Huffman Tree ; A node of huffman tree ; Structure for Queue : collection of Huffman Tree nodes ( or QueueNodes ) ; A utility function to create a new Queuenode ; A utility function to create a Queue of given capacity ; A utility function to check if size of given queue is 1 ; A utility function to check if given queue is empty ; A utility function to check if given queue is full ; A utility function to add an item to queue ; A utility function to remove an item from queue ; If there is only one item in queue ; A utility function to get from of queue ; A function to get minimum item from two queues ; Step 3. a : If first queue is empty , dequeue from second queue ; Step 3. b : If second queue is empty , dequeue from first queue ; Step 3. c : Else , compare the front of two queues and dequeue minimum ; Utility function to check if this node is leaf ; A utility function to print an array of size n ; The main function that builds Huffman tree ; Step 1 : Create two empty queues ; Step 2 : Create a leaf node for each unique character and Enqueue it to the first queue in non - decreasing order of frequency . Initially second queue is empty ; Run while Queues contain more than one node . Finally , first queue will be empty and second queue will contain only one node ; Step 3 : Dequeue two nodes with the minimum frequency by examining the front of both queues ; Step 4 : Create a new internal node with frequency equal to the sum of the two nodes frequencies . Enqueue this node to second queue . ; Prints huffman codes from the root of Huffman Tree . It uses arr [ ] to store codes ; Assign 0 to left edge and recur ; Assign 1 to right edge and recur ; If this is a leaf node , then it contains one of the input characters , print the character and its code from arr [ ] ; The main function that builds a Huffman Tree and print codes by traversing the built Huffman Tree ; Construct Huffman Tree ; Print Huffman codes using the Huffman tree built above ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define MAX_TREE_HT  100 NEW_LINE class QueueNode { public : char data ; unsigned freq ; QueueNode * left , * right ; } ; class Queue { public : int front , rear ; int capacity ; QueueNode * * array ; } ; QueueNode * newNode ( char data , unsigned freq ) { QueueNode * temp = new QueueNode [ ( sizeof ( QueueNode ) ) ] ; temp -> left = temp -> right = NULL ; temp -> data = data ; temp -> freq = freq ; return temp ; } Queue * createQueue ( int capacity ) { Queue * queue = new Queue [ ( sizeof ( Queue ) ) ] ; queue -> front = queue -> rear = -1 ; queue -> capacity = capacity ; queue -> array = new QueueNode * [ ( queue -> capacity * sizeof ( QueueNode * ) ) ] ; return queue ; } int isSizeOne ( Queue * queue ) { return queue -> front == queue -> rear && queue -> front != -1 ; } int isEmpty ( Queue * queue ) { return queue -> front == -1 ; } int isFull ( Queue * queue ) { return queue -> rear == queue -> capacity - 1 ; } void enQueue ( Queue * queue , QueueNode * item ) { if ( isFull ( queue ) ) return ; queue -> array [ ++ queue -> rear ] = item ; if ( queue -> front == -1 ) ++ queue -> front ; } QueueNode * deQueue ( Queue * queue ) { if ( isEmpty ( queue ) ) return NULL ; QueueNode * temp = queue -> array [ queue -> front ] ; if ( queue -> front == queue -> rear ) queue -> front = queue -> rear = -1 ; else ++ queue -> front ; return temp ; } QueueNode * getFront ( Queue * queue ) { if ( isEmpty ( queue ) ) return NULL ; return queue -> array [ queue -> front ] ; } QueueNode * findMin ( Queue * firstQueue , Queue * secondQueue ) { if ( isEmpty ( firstQueue ) ) return deQueue ( secondQueue ) ; if ( isEmpty ( secondQueue ) ) return deQueue ( firstQueue ) ; if ( getFront ( firstQueue ) -> freq < getFront ( secondQueue ) -> freq ) return deQueue ( firstQueue ) ; return deQueue ( secondQueue ) ; } int isLeaf ( QueueNode * root ) { return ! ( root -> left ) && ! ( root -> right ) ; } void printArr ( int arr [ ] , int n ) { int i ; for ( i = 0 ; i < n ; ++ i ) cout << arr [ i ] ; cout << endl ; } QueueNode * buildHuffmanTree ( char data [ ] , int freq [ ] , int size ) { QueueNode * left , * right , * top ; Queue * firstQueue = createQueue ( size ) ; Queue * secondQueue = createQueue ( size ) ; for ( int i = 0 ; i < size ; ++ i ) enQueue ( firstQueue , newNode ( data [ i ] , freq [ i ] ) ) ; while ( ! ( isEmpty ( firstQueue ) && isSizeOne ( secondQueue ) ) ) { left = findMin ( firstQueue , secondQueue ) ; right = findMin ( firstQueue , secondQueue ) ; top = newNode ( ' $ ' , left -> freq + right -> freq ) ; top -> left = left ; top -> right = right ; enQueue ( secondQueue , top ) ; } return deQueue ( secondQueue ) ; } void printCodes ( QueueNode * root , int arr [ ] , int top ) { if ( root -> left ) { arr [ top ] = 0 ; printCodes ( root -> left , arr , top + 1 ) ; } if ( root -> right ) { arr [ top ] = 1 ; printCodes ( root -> right , arr , top + 1 ) ; } if ( isLeaf ( root ) ) { cout << root -> data << " : ▁ " ; printArr ( arr , top ) ; } } void HuffmanCodes ( char data [ ] , int freq [ ] , int size ) { QueueNode * root = buildHuffmanTree ( data , freq , size ) ; int arr [ MAX_TREE_HT ] , top = 0 ; printCodes ( root , arr , top ) ; } int main ( ) { char arr [ ] = { ' a ' , ' b ' , ' c ' , ' d ' , ' e ' , ' f ' } ; int freq [ ] = { 5 , 9 , 12 , 13 , 16 , 45 } ; int size = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; HuffmanCodes ( arr , freq , size ) ; return 0 ; }