An Optimal‚ Purely Functional Implementation of the Garsia−Wachs Algorithm

Abstract

The Garsia–Wachs algorithm is an algorithm for building a binary leaf tree whose cost is as small as possible. The problem and the algorithm are described in more detail below, but the task is essentially the same as that of building a Huffman coding tree with the added constraint that the fringe of the tree has to be exactly the given list of inputs (in Huffman coding, the fringe of the tree can be any permutation of the input). As we will show below, the Garsia–Wachs algorithm can be implemented with a linearithmic running time—a running time of O (n log n) steps for an input of length n, the same time bound as for Huffman coding.