{"id":25081,"date":"2017-10-15T14:11:55","date_gmt":"2017-10-15T08:41:55","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=25081"},"modified":"2017-10-15T14:11:55","modified_gmt":"2017-10-15T08:41:55","slug":"efficient-huffman-coding-sorted-input","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/efficient-huffman-coding-sorted-input\/","title":{"rendered":"Efficient Huffman Coding for Sorted Input"},"content":{"rendered":"

We recommend to read following post as a prerequisite for this.<\/p>\n

Huffman Coding<\/p>\n

Time complexity of the algorithm discussed in above post is O(nLogn). <\/span>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.<\/p>\n

1.<\/strong> Create two empty queues.<\/p>\n

2.<\/strong> 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.<\/p>\n

3.<\/strong> Dequeue two nodes with the minimum frequency by examining the front of both queues. Repeat following steps two times
\n\u2026..a)<\/strong> If second queue is empty, dequeue from first queue.
\n\u2026..b)<\/strong> If first queue is empty, dequeue from second queue.
\n\u2026..c)<\/strong> Else, compare the front of two queues and dequeue the minimum.<\/p>\n

4.<\/strong> 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.<\/p>\n

5.<\/strong> 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.<\/p>\n[pastacode lang=\u201dc\u201d manual=\u201d%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(\u2018%24\u2019%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\u2019a\u2019%2C%20\u2019b\u2019%2C%20\u2019c\u2019%2C%20\u2019d\u2019%2C%20\u2019e\u2019%2C%20\u2019f\u2019%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\u201d message=\u201dc\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n

Output:<\/strong><\/h4>\n
f: 0\r\nc: 100\r\nd: 101\r\na: 1100\r\nb: 1101\r\ne: 111<\/pre>\n
Time complexity:<\/strong> O(n)<\/p>\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.<\/p>\n[ad type=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":"
Efficient Huffman Coding for Sorted Input – Greedy Algorithm – 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).<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1,83476],"tags":[71215,71202,71082,71195,71197,71090,71067,71203,71084,71200,71208,71207,71199,71097,71113,71114,71068,71119,71209,70480,71079,71112,71116,71083,71085,71204,71103,71091,71108,71101,71201,71089,71100,71107,71213,71086,71206,71080,71088,71118,71214,71205,71212,71211,71115,71087,71099,71105,71109,71092,71117,71210,71193,71194,71111,71073,71064,71071,71192,71196,71198,71102],"class_list":["post-25081","post","type-post","status-publish","format-standard","hentry","category-coding","category-huffman-coding","tag-adaptive-huffman-coding-in-c","tag-adaptive-huffman-coding-tree-example","tag-application-of-huffman-coding-in-data-compression","tag-arithmetic-coding-for-data-compression-example","tag-binary-code-example","tag-c-program-to-implement-huffman-code","tag-codetree","tag-coding-algorithms","tag-encoding-and-decoding-huffman-code-in-java","tag-example-of-encoding","tag-example-of-huffman-coding","tag-examples-of-trees","tag-ffman-coding-in-c-huffman-program-in-c","tag-frequency-tree","tag-half-man-coding","tag-how-to-find-codeword-in-huffman-coding","tag-huffman-algorithm-in-data-structure","tag-huffman-algorithm-java","tag-huffman-code-tree-generator","tag-huffman-coding","tag-huffman-coding-algorithm-in-c","tag-huffman-coding-algorithm-in-matlab","tag-huffman-coding-animation","tag-huffman-coding-example","tag-huffman-coding-example-pdf","tag-huffman-coding-implementation","tag-huffman-coding-in-c-language","tag-huffman-coding-in-c-using-array","tag-huffman-coding-in-matlab-program","tag-huffman-coding-matlab-program","tag-huffman-coding-ppt-presentation","tag-huffman-coding-program-in-c","tag-huffman-coding-program-in-c-with-output","tag-huffman-coding-program-in-java","tag-huffman-coding-simple-program-in-c","tag-huffman-coding-steps","tag-huffman-coding-using-matlab","tag-huffman-coding-with-example","tag-huffman-compression-algorithm","tag-huffman-encoding-and-decoding-example-in-java","tag-huffman-encoding-and-decoding-in-c","tag-huffman-encoding-and-decoding-in-matlab","tag-huffman-encoding-in-c","tag-huffman-encoding-online","tag-huffman-encoding-tree","tag-huffman-tree","tag-huffman-tree-c","tag-implementation-of-huffman-coding-in-c","tag-online-huffman-encoder","tag-optimal-huffman-code","tag-program-for-huffman-coding-in-c","tag-shannon-coding-example","tag-shannon-fano-algorithm","tag-shannon-fano-coding-example","tag-simple-huffman-coding-c","tag-simple-huffman-coding-in-c","tag-source-code-for-huffman-coding-in-c","tag-tree-code","tag-tree-tutorial","tag-variance-symbol","tag-write-a-program-for-hu","tag-write-a-program-for-huffman-coding"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25081","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=25081"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25081\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=25081"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=25081"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=25081"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}