A New Algorithm for Building Alphabetic Minimax Trees
Travis Gagie · Fundamenta Informaticae · 2009
We show how to build an alphabetic minimax tree for a sequence W = w, …, w of real weights in O(nd log log n) time, where d is the number of distinct integers ⌈wi⌉. We apply this algorithm to building an alphabetic prefix code given a sample.