Huffman Coding with Non-Sorted Frequencies

Abstract. A standard way of implementing Huffman’s optimal code construction al-gorithm is by using a sorted sequence of frequencies. Several aspects of the algorithm are investigated as to the consequences of relaxing the requirement of keeping the fre-quencies in order. Using only partial order may speed up the code construction, which is important in some applications, at the cost of increasing the size of the encoded file.