Write a program to generate a Huffman tree and corresponding message codes. Build a min$-$heap keyed with the frequencies.

Output the message code for each frequency, as well as the total weighted external path length for the tree.

Run for the frequencies of $($select three of A$,$ B$,$ C and D$)$:

A$.$ the English alphabet, as given in Moret and Shapiro p$.294,$ Figure $5\mathrm{.}9$;

B$.$ Cyrillic symbols; see the symbols and frequencies;

C$.$ Hiragana syllabic symbols in the Japanese writing system; see a list of symbols and frequencies. Calculate the frequencies more accurately based on the Count and Total count, e$.$g$.,$ for the first frequency listed: $645670/10182184=0\mathrm{.}063412,$ and for the last one, $386/10182184=0\mathrm{.}000038.$

D$.$ Arabic letters; see symbols and frequencies.

Generate sets of n frequencies at random and run your program for increasing n$.$ Time the execution of $(1)$ building the initial heap keyed with the frequencies ; and $(2)$ the complete generation of the Huffman tree. Graph the times as a function of n$.$

Notes: $($a$)$ To get more accurate results, you can repeat the Huffman tree construction a number of times and use the average time. $($b$)$ The size of the problem should not be limited by the use of static arrays $($use dynamic memory allocation$).$

Your report should include a comparison of the observed performance with the expected theoretical behavior. Note that the building of the heap should be done in linear time.