科研之友
微信
新浪微博
Facebook
分享链接
摘要
A minimax tree is similar to a Huffman tree except that, instead of minimizing the weighted average of the leaves%26apos; depths, it minimizes the maximum of any leaf%26apos;s weight plus its depth. Golumbic (1976) [20] introduced minimax trees and gave a Huffman-like, O(n log n)-time algorithm for building them. Drmota and Szpankowski (2002)[10] gave another O(n log n)-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.
- 出版日期2013-1
