In-place calculation of minimum-redundancy codes

Abstract

The optimal prefix-free code problem is to determine, for a given array p = \pi\i € {1… n] of n weights, an integer array I = [it | i 6 {1… n] of n codeword lengths such that ^"=12-,i < 1 and ICfci Pilis mmimized. Huffman's famous greedy algorithm solves this problem in 0(n log n) time, if p is unsorted; and can be implemented to execute in 0(n) time, if the input array p is sorted. Here we consider the space requirements of the greedy method. We show that if p is sorted then it is possible to calculate the array I in-place, with U overwriting pi, in O(n) time and using 0(1) additional space. The new implementation leads directly to an 0(n log n)-time and n + 0(1) words of extra space implem..