(acharacter frequency (ba figure an illustration of an example huffman code for the input string " fast runner need never be afraid of the dark"(afrequency of each character of (bhuffman tree for string the code for character is obtained by tracing the path from the root of to the leaf where is storedand associating left child with and right child with for examplethe code for "ris and the code for "his the huffman coding algorithm the huffman coding algorithm begins with each of the distinct characters of the string to encode being the root node of single-node binary tree the algorithm proceeds in series of rounds in each roundthe algorithm takes the two binary trees with the smallest frequencies and merges them into single binary tree it repeats this process until only one tree is left (see code fragment each iteration of the while loop in huffman' algorithm can be implemented in (log dtime using priority queue represented with heap in additioneach iteration takes two nodes out of and adds one ina process that will be repeated times before exactly one node is left in thusthis algorithm runs in ( log dtime although full justification of this algorithm' correctness is beyond our scope herewe note that its intuition comes from simple idea--any optimal code can be converted into an optimal code in which the code-words for the two lowest-frequency charactersa and bdiffer only in their last bit repeating the argument for string with and replaced by character cgives the followingproposition huffman' algorithm constructs an optimal prefix code for string of length with distinct characters in ( log dtime