# Optimal Prefix Free Codes with Partial Sorting +
## 2 Solution
### General Intuition  
Observing that the algorithm suggested by [PERSON] [1] in 1952 always creates the internal nodes in increasing order of weight, [PERSON] [14] described in 1976 an algorithm to compute optimal prefix free codes in linear time when the input (i.e., the weights of the external nodes) is given in sorted order. A close look at the execution of [PERSON]'s algorithm [14] reveals a sequence of sequential searches for the insertion rank \(r\) of the weight of some internal node in the list of weights of external nodes. Such sequential search could be replaced by a more efficient search algorithm in  
returnred is always (for \(n>1\)) an internal node. The two last properties are simple consequences of the fact that \(\mathcal{S}\) is a binary string starting with an \(E\) and finishing with an \(I\). **Example 2**. : _For example, consider the text \(T=\)\"ABBCCCDDDDEEEFFFFGGGGGGGHHHHHHH\" formed by the concatenation of one occurrence of \"A\", two occurrences of \"B\", three occurrences of \"C\", four occurrences of \"D\", five occurrences of \"E\", five (again) occurrences of \"F\", six occurrences of \"G\" and seven occurrences of \"H\", so that the corresponding frequencies are \(W=\left[ \begin{array}{cc}1&2&3&4&5&5&6&7\end{array} \right]\). It corresponds to an instance of size \(n=8\), of \(E\)I signature \(\mathcal{S}(W)=\mathbf{EE}\boxplus\mathbf{EE}\boxplus\mathbf{EE}\boxplus \mathbf{EI}\boxplus\mathbf{III}\) of length \(15\), which starts with \(\mathbf{EE}\), finishes with \(I\), and contains only \(\alpha=3\) occurrences of \(\boxplus\mathbf{I}\) (underlined), corresponding to a decomposition into \(\alpha=3\) maximal blocks of consecutive \(\mathbf{Es}\) (in bold), out of a maximal potential number of \(7\) for the alphabet size \(n=8\)._  
Instances such as that presented in Example 2, with very few blocks of \(E\) (more than in Example 3, but much less than in the worst case), are easier to solve than instances with many such blocks. For example, an instance \(W\) of length \(n\) such that its \(\mathrm{EI}\) signature \(\mathcal{S}(W)\) is composed of a single run of \(n\)\(\mathrm{Es}\) followed by a single run of \(n-1\)\(\mathrm{Is}\) (such as the one described in Figure 1) can be solved in linear time, and in particular without sorting the weights: it is enough to assign the codelength \(l=\left\lfloor\log_{2}n\right\rfloor\) to the \(n-2^{l}\) largest weights and the codelength \(l+1\) to the \(2^{l}\) smallest weights. Separating those weights is a simple select operation, supported in amortized linear time by the data structures described in the following section. We describe two other extreme examples, starting with one where all the weights are equal (as a particular case of when they are all within a factor of two of each other). **Example 3**. : _Consider the text \(T=\)\"ba_bb_caca_ba_cc\" from Figure 1. Each of the four messages (input symbols) of its alphabet \(\left\{a,b,c,\_\right\}\) occurs exactly \(4\) times, so that an optimal prefix free code assigns a uniform codelength of \(2\) bits to all messages (see Figure 1). There is no need to sort the messages by frequency (and the prefix free code does not yield any information about the order in which the messages would be sorted by monotone frequencies), and accordingly the \(\mathrm{EI}\) signature of this text, \(\mathcal{S}(T)=\)\"\(\mathbf{EEE}\boxplus\mathbf{II}\)\", has a single block of \(\mathit{Es}\), indicating a very easy instance. The same holds if the text is such that the frequencies of the messages are all within a factor of two of each other._  
On the other hand, some instances present the opposite extreme, where no weight is within a factor of two of any other, which \"forces\" any algorithm computing optimal prefix free codes to sort the weights. **Example 4**.