We consider the following Variant of Huffman coding in which the costs
of the letters, rather than the probabilities of the words, are nonun
iform: ''Given an alphabet of r letters of nonuniform length, find a m
inimum-average-length prefix-free set of n codewords over the alphabet
''; equivalently, ''Find an optimal r-ary search tree with n leaves, w
here each leaf is accessed with equal probability but the cost to desc
end from a parent to its ith child depends on i.'' We show new structu
ral properties of such codes, leading to an O(nlog(2) r)-time algorith
m for finding them, This new algorithm is simpler and faster than the
best previously known O(nr min{logn, r})-time algorithm, due to Perl,
Garey, and Even [J. Assoc, Comput. Mach., 22 (1975), pp. 202-214].