Minimax trees in linear time with applications (Q1761500)

In a minimax tree for a multiset \(W=\{w_1,\dots,w_n\}\) of weights, each leaf has a weight \(w_i\), each internal node has weight equal to the maximum of its children's weights plus 1, and the weight of the root is as small as possible. A minimax tree is thus similar to a Huffman tree which minimizes the weighted average of the leaves' depths. Golumbic (1976) [\textit{M.C. Golumbic}, ``Combinatorial merging,'' IEEE Trans. Comput. 25, 1164--1167 (1976; Zbl 0364.94037)] introduced minimax trees and gave a Huffman-like, \(\mathcal O(n\log n)\)-time algorithm for building them. Drmota and Szpankowski (2002) [\textit{M. Drmota} and \textit{W. Szpankowski}, ``Generalized Shannon code minimizes the maximal redundancy,'' Lect. Notes Comput. Sci. 2286, 306--318 (2002; Zbl 1068.94006)] gave another \(\mathcal O(n\log n)\)-time algorithm, which takes linear time when the weights are already sorted by their fractional parts. Main result of this paper is the first linear-time algorithm for building minimax trees for unsorted real weights. This algorithm is based on Drmota and Szpankowski's but, whereas their algorithm uses sorting and binary search, the new one uses generalized selection, as well as a new data structure to test the Kraft inequality. The paper concludes with an application of the presented algorithm to problems in adaptive and semi-static prefix coding and group testing.