Minimax trees in linear time with applications (Q1761500)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Minimax trees in linear time with applications |
scientific article |
Statements
Minimax trees in linear time with applications (English)
0 references
15 November 2012
0 references
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.
0 references
trees
0 references
coding theorems
0 references
minimax trees
0 references
adaptive coding
0 references
Huffman tree
0 references
semi-static prefix coding
0 references
group testing
0 references