An optimal, purely functional implementation of the Garsia–Wachs algorithm. (21st January 2020)

• Record Type: Journal Article
• Authors: BIRD, RICHARD S.
• Is Part Of: Journal of functional programming. Volume 30(2020)
• Publication Date: 2020-01-21
• Subjects: Functional programming (Computer science) -- Periodicals
• DOI: 10.1017/S0956796819000194
• Languages: English
• ISSNs: 0956-7968

Abstract

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.