how to prove that the lower bound of the Huffman coding problem is $\Omega(n \log n)$?
Here Huffman coding problem is Huffman encoding.
Input: A string with different characters, say “ACCEBFFFFAAXXBLKE” Output: Code for different characters: Data: K, Frequency: 1, Code: 0000 Data: L, Frequency: 1, Code: 0001 Data: E, Frequency: 2, Code: 001 Data: F, Frequency: 4, Code: 01 Data: B, Frequency: 2, Code: 100 Data: C, Frequency: 2, Code: 101 Data: X, Frequency: 2, Code: 110 Data: A, Frequency: 3, Code: 111
I already saw that we can know that the bound of the sorting problem is $\Omega(n \log n)$ by using decision tree.
the number of leaves: $n!$
(the number of leaves in a half tree with a height of $h) \leq 2^h$
$\Rightarrow n! \leq 2^h \Rightarrow h \geq \log n!$
$\Rightarrow \log n! \fallingdotseq n \log n - n = \Omega(n \log n)$
So I thought I could also use the decision tree to get the lower bound of the Huffman coding problem but I am not sure how to construct the decision tree for Huffman coding problem, like how many leaves are needed,...
Please tell me how to construct the decision tree or is my attempt to tackle this proof wrong?