We recommend to read following post as a prerequisite for this.
Huffman Coding
Time complexity of the algorithm discussed in above post is O(nLogn). If we know that the given array is sorted (by non-decreasing order of frequency), we can generate Huffman codes in O(n) time. Following is a O(n) algorithm for sorted input.
1. Create two empty queues.
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.
3. Dequeue two nodes with the minimum frequency by examining the front of both queues. Repeat following steps two times
…..a) If second queue is empty, dequeue from first queue.
…..b) If first queue is empty, dequeue from second queue.
…..c) Else, compare the front of two queues and dequeue the minimum.
4. Create a new internal node with frequency equal to the sum of the two nodes frequencies. Make the first Dequeued node as its left child and the second Dequeued node as right child. Enqueue this node to second queue.
5. Repeat steps#3 and #4 until there is more than one node in the queues. The remaining node is the root node and the tree is complete.
[pastacode lang=”c” manual=”%2F%2F%20C%20Program%20for%20Efficient%20Huffman%20Coding%20for%20Sorted%20input%0A%23include%20%3Cstdio.h%3E%0A%23include%20%3Cstdlib.h%3E%0A%20%0A%2F%2F%20This%20constant%20can%20be%20avoided%20by%20explicitly%20calculating%20height%20of%20Huffman%20Tree%0A%23define%20MAX_TREE_HT%20100%0A%20%0A%2F%2F%20A%20node%20of%20huffman%20tree%0Astruct%20QueueNode%0A%7B%0A%20%20%20%20char%20data%3B%0A%20%20%20%20unsigned%20freq%3B%0A%20%20%20%20struct%20QueueNode%20*left%2C%20*right%3B%0A%7D%3B%0A%20%0A%2F%2F%20Structure%20for%20Queue%3A%20collection%20of%20Huffman%20Tree%20nodes%20(or%20QueueNodes)%0Astruct%20Queue%0A%7B%0A%20%20%20%20int%20front%2C%20rear%3B%0A%20%20%20%20int%20capacity%3B%0A%20%20%20%20struct%20QueueNode%20**array%3B%0A%7D%3B%0A%20%0A%2F%2F%20A%20utility%20function%20to%20create%20a%20new%20Queuenode%0Astruct%20QueueNode*%20newNode(char%20data%2C%20unsigned%20freq)%0A%7B%0A%20%20%20%20struct%20QueueNode*%20temp%20%3D%0A%20%20%20%20%20%20%20(struct%20QueueNode*)%20malloc(sizeof(struct%20QueueNode))%3B%0A%20%20%20%20temp-%3Eleft%20%3D%20temp-%3Eright%20%3D%20NULL%3B%0A%20%20%20%20temp-%3Edata%20%3D%20data%3B%0A%20%20%20%20temp-%3Efreq%20%3D%20freq%3B%0A%20%20%20%20return%20temp%3B%0A%7D%0A%20%0A%2F%2F%20A%20utility%20function%20to%20create%20a%20Queue%20of%20given%20capacity%0Astruct%20Queue*%20createQueue(int%20capacity)%0A%7B%0A%20%20%20%20struct%20Queue*%20queue%20%3D%20(struct%20Queue*)%20malloc(sizeof(struct%20Queue))%3B%0A%20%20%20%20queue-%3Efront%20%3D%20queue-%3Erear%20%3D%20-1%3B%0A%20%20%20%20queue-%3Ecapacity%20%3D%20capacity%3B%0A%20%20%20%20queue-%3Earray%20%3D%0A%20%20%20%20%20%20(struct%20QueueNode**)%20malloc(queue-%3Ecapacity%20*%20sizeof(struct%20QueueNode*))%3B%0A%20%20%20%20return%20queue%3B%0A%7D%0A%20%0A%2F%2F%20A%20utility%20function%20to%20check%20if%20size%20of%20given%20queue%20is%201%0Aint%20isSizeOne(struct%20Queue*%20queue)%0A%7B%0A%20%20%20%20return%20queue-%3Efront%20%3D%3D%20queue-%3Erear%20%26%26%20queue-%3Efront%20!%3D%20-1%3B%0A%7D%0A%20%0A%2F%2F%20A%20utility%20function%20to%20check%20if%20given%20queue%20is%20empty%0Aint%20isEmpty(struct%20Queue*%20queue)%0A%7B%0A%20%20%20%20return%20queue-%3Efront%20%3D%3D%20-1%3B%0A%7D%0A%20%0A%2F%2F%20A%20utility%20function%20to%20check%20if%20given%20queue%20is%20full%0Aint%20isFull(struct%20Queue*%20queue)%0A%7B%0A%20%20%20%20return%20queue-%3Erear%20%3D%3D%20queue-%3Ecapacity%20-%201%3B%0A%7D%0A%20%0A%2F%2F%20A%20utility%20function%20to%20add%20an%20item%20to%20queue%0Avoid%20enQueue(struct%20Queue*%20queue%2C%20struct%20QueueNode*%20item)%0A%7B%0A%20%20%20%20if%20(isFull(queue))%0A%20%20%20%20%20%20%20%20return%3B%0A%20%20%20%20queue-%3Earray%5B%2B%2Bqueue-%3Erear%5D%20%3D%20item%3B%0A%20%20%20%20if%20(queue-%3Efront%20%3D%3D%20-1)%0A%20%20%20%20%20%20%20%20%2B%2Bqueue-%3Efront%3B%0A%7D%0A%20%0A%2F%2F%20A%20utility%20function%20to%20remove%20an%20item%20from%20queue%0Astruct%20QueueNode*%20deQueue(struct%20Queue*%20queue)%0A%7B%0A%20%20%20%20if%20(isEmpty(queue))%0A%20%20%20%20%20%20%20%20return%20NULL%3B%0A%20%20%20%20struct%20QueueNode*%20temp%20%3D%20queue-%3Earray%5Bqueue-%3Efront%5D%3B%0A%20%20%20%20if%20(queue-%3Efront%20%3D%3D%20queue-%3Erear)%20%20%2F%2F%20If%20there%20is%20only%20one%20item%20in%20queue%0A%20%20%20%20%20%20%20%20queue-%3Efront%20%3D%20queue-%3Erear%20%3D%20-1%3B%0A%20%20%20%20else%0A%20%20%20%20%20%20%20%20%2B%2Bqueue-%3Efront%3B%0A%20%20%20%20return%20temp%3B%0A%7D%0A%20%0A%2F%2F%20A%20utility%20function%20to%20get%20from%20of%20queue%0Astruct%20QueueNode*%20getFront(struct%20Queue*%20queue)%0A%7B%0A%20%20%20%20if%20(isEmpty(queue))%0A%20%20%20%20%20%20%20%20return%20NULL%3B%0A%20%20%20%20return%20queue-%3Earray%5Bqueue-%3Efront%5D%3B%0A%7D%0A%20%0A%2F*%20A%20function%20to%20get%20minimum%20item%20from%20two%20queues%20*%2F%0Astruct%20QueueNode*%20findMin(struct%20Queue*%20firstQueue%2C%20struct%20Queue*%20secondQueue)%0A%7B%0A%20%20%20%20%2F%2F%20Step%203.a%3A%20If%20second%20queue%20is%20empty%2C%20dequeue%20from%20first%20queue%0A%20%20%20%20if%20(isEmpty(firstQueue))%0A%20%20%20%20%20%20%20%20return%20deQueue(secondQueue)%3B%0A%20%0A%20%20%20%20%2F%2F%20Step%203.b%3A%20If%20first%20queue%20is%20empty%2C%20dequeue%20from%20second%20queue%0A%20%20%20%20if%20(isEmpty(secondQueue))%0A%20%20%20%20%20%20%20%20return%20deQueue(firstQueue)%3B%0A%20%0A%20%20%20%20%2F%2F%20Step%203.c%3A%20%20Else%2C%20compare%20the%20front%20of%20two%20queues%20and%20dequeue%20minimum%0A%20%20%20%20if%20(getFront(firstQueue)-%3Efreq%20%3C%20getFront(secondQueue)-%3Efreq)%0A%20%20%20%20%20%20%20%20return%20deQueue(firstQueue)%3B%0A%20%0A%20%20%20%20return%20deQueue(secondQueue)%3B%0A%7D%0A%20%0A%2F%2F%20Utility%20function%20to%20check%20if%20this%20node%20is%20leaf%0Aint%20isLeaf(struct%20QueueNode*%20root)%0A%7B%0A%20%20%20%20return%20!(root-%3Eleft)%20%26%26%20!(root-%3Eright)%20%3B%0A%7D%0A%20%0A%2F%2F%20A%20utility%20function%20to%20print%20an%20array%20of%20size%20n%0Avoid%20printArr(int%20arr%5B%5D%2C%20int%20n)%0A%7B%0A%20%20%20%20int%20i%3B%0A%20%20%20%20for%20(i%20%3D%200%3B%20i%20%3C%20n%3B%20%2B%2Bi)%0A%20%20%20%20%20%20%20%20printf(%22%25d%22%2C%20arr%5Bi%5D)%3B%0A%20%20%20%20printf(%22%5Cn%22)%3B%0A%7D%0A%20%0A%2F%2F%20The%20main%20function%20that%20builds%20Huffman%20tree%0Astruct%20QueueNode*%20buildHuffmanTree(char%20data%5B%5D%2C%20int%20freq%5B%5D%2C%20int%20size)%0A%7B%0A%20%20%20%20struct%20QueueNode%20*left%2C%20*right%2C%20*top%3B%0A%20%0A%20%20%20%20%2F%2F%20Step%201%3A%20Create%20two%20empty%20queues%0A%20%20%20%20struct%20Queue*%20firstQueue%20%20%3D%20createQueue(size)%3B%0A%20%20%20%20struct%20Queue*%20secondQueue%20%3D%20createQueue(size)%3B%0A%20%0A%20%20%20%20%2F%2F%20Step%202%3ACreate%20a%20leaf%20node%20for%20each%20unique%20character%20and%20Enqueue%20it%20to%0A%20%20%20%20%2F%2F%20the%20first%20queue%20in%20non-decreasing%20order%20of%20frequency.%20Initially%20second%0A%20%20%20%20%2F%2F%20queue%20is%20empty%0A%20%20%20%20for%20(int%20i%20%3D%200%3B%20i%20%3C%20size%3B%20%2B%2Bi)%0A%20%20%20%20%20%20%20%20enQueue(firstQueue%2C%20newNode(data%5Bi%5D%2C%20freq%5Bi%5D))%3B%0A%20%0A%20%20%20%20%2F%2F%20Run%20while%20Queues%20contain%20more%20than%20one%20node.%20Finally%2C%20first%20queue%20will%0A%20%20%20%20%2F%2F%20be%20empty%20and%20second%20queue%20will%20contain%20only%20one%20node%0A%20%20%20%20while%20(!(isEmpty(firstQueue)%20%26%26%20isSizeOne(secondQueue)))%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20Step%203%3A%20Dequeue%20two%20nodes%20with%20the%20minimum%20frequency%20by%20examining%0A%20%20%20%20%20%20%20%20%2F%2F%20the%20front%20of%20both%20queues%0A%20%20%20%20%20%20%20%20left%20%3D%20findMin(firstQueue%2C%20secondQueue)%3B%0A%20%20%20%20%20%20%20%20right%20%3D%20findMin(firstQueue%2C%20secondQueue)%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Step%204%3A%20Create%20a%20new%20internal%20node%20with%20frequency%20equal%20to%20the%20sum%0A%20%20%20%20%20%20%20%20%2F%2F%20of%20the%20two%20nodes%20frequencies.%20Enqueue%20this%20node%20to%20second%20queue.%0A%20%20%20%20%20%20%20%20top%20%3D%20newNode(‘%24’%20%2C%20left-%3Efreq%20%2B%20right-%3Efreq)%3B%0A%20%20%20%20%20%20%20%20top-%3Eleft%20%3D%20left%3B%0A%20%20%20%20%20%20%20%20top-%3Eright%20%3D%20right%3B%0A%20%20%20%20%20%20%20%20enQueue(secondQueue%2C%20top)%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20return%20deQueue(secondQueue)%3B%0A%7D%0A%20%0A%2F%2F%20Prints%20huffman%20codes%20from%20the%20root%20of%20Huffman%20Tree.%20%20It%20uses%20arr%5B%5D%20to%0A%2F%2F%20store%20codes%0Avoid%20printCodes(struct%20QueueNode*%20root%2C%20int%20arr%5B%5D%2C%20int%20top)%0A%7B%0A%20%20%20%20%2F%2F%20Assign%200%20to%20left%20edge%20and%20recur%0A%20%20%20%20if%20(root-%3Eleft)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20arr%5Btop%5D%20%3D%200%3B%0A%20%20%20%20%20%20%20%20printCodes(root-%3Eleft%2C%20arr%2C%20top%20%2B%201)%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20Assign%201%20to%20right%20edge%20and%20recur%0A%20%20%20%20if%20(root-%3Eright)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20arr%5Btop%5D%20%3D%201%3B%0A%20%20%20%20%20%20%20%20printCodes(root-%3Eright%2C%20arr%2C%20top%20%2B%201)%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20If%20this%20is%20a%20leaf%20node%2C%20then%20it%20contains%20one%20of%20the%20input%0A%20%20%20%20%2F%2F%20characters%2C%20print%20the%20character%20and%20its%20code%20from%20arr%5B%5D%0A%20%20%20%20if%20(isLeaf(root))%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20printf(%22%25c%3A%20%22%2C%20root-%3Edata)%3B%0A%20%20%20%20%20%20%20%20printArr(arr%2C%20top)%3B%0A%20%20%20%20%7D%0A%7D%0A%20%0A%2F%2F%20The%20main%20function%20that%20builds%20a%20Huffman%20Tree%20and%20print%20codes%20by%20traversing%0A%2F%2F%20the%20built%20Huffman%20Tree%0Avoid%20HuffmanCodes(char%20data%5B%5D%2C%20int%20freq%5B%5D%2C%20int%20size)%0A%7B%0A%20%20%20%2F%2F%20%20Construct%20Huffman%20Tree%0A%20%20%20struct%20QueueNode*%20root%20%3D%20buildHuffmanTree(data%2C%20freq%2C%20size)%3B%0A%20%0A%20%20%20%2F%2F%20Print%20Huffman%20codes%20using%20the%20Huffman%20tree%20built%20above%0A%20%20%20int%20arr%5BMAX_TREE_HT%5D%2C%20top%20%3D%200%3B%0A%20%20%20printCodes(root%2C%20arr%2C%20top)%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20above%20functions%0Aint%20main()%0A%7B%0A%20%20%20%20char%20arr%5B%5D%20%3D%20%7B’a’%2C%20’b’%2C%20’c’%2C%20’d’%2C%20’e’%2C%20’f’%7D%3B%0A%20%20%20%20int%20freq%5B%5D%20%3D%20%7B5%2C%209%2C%2012%2C%2013%2C%2016%2C%2045%7D%3B%0A%20%20%20%20int%20size%20%3D%20sizeof(arr)%2Fsizeof(arr%5B0%5D)%3B%0A%20%20%20%20HuffmanCodes(arr%2C%20freq%2C%20size)%3B%0A%20%20%20%20return%200%3B%0A%7D%0ARun%20on%20IDE%0A” message=”c” highlight=”” provider=”manual”/]Output:
f: 0 c: 100 d: 101 a: 1100 b: 1101 e: 111
Time complexity: O(n)
If the input is not sorted, it need to be sorted first before it can be processed by the above algorithm. Sorting can be done using heap-sort or merge-sort both of which run in Theta(nlogn). So, the overall time complexity becomes O(nlogn) for unsorted input.
[ad type=”banner”]