Photo by starofthesea7 from unsplash
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,… Click to show full 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.
Journal Title: Journal of Functional Programming
Year Published: 2020
Link to full text (if available)
Share on Social Media: Sign Up to like & get
recommendations!