Minimax trees in linear time with applications

A minimax tree is similar to a Huffman tree except that, instead of minimizing the weighted average of the leaves' depths, it minimizes the maximum of any leaf's weight plus its depth. Golumbic (1976) [20] introduced minimax trees and gave a Huffman-like, O(nlogn)-time algorithm for building them. Drmota and Szpankowski (2002) [10] gave another O(nlogn)-time algorithm, which takes linear time when the weights are already sorted by their fractional parts. In this paper we give the first linear-time algorithm for building minimax trees for unsorted real weights.