{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,26]],"date-time":"2026-05-26T23:06:01Z","timestamp":1779836761044,"version":"3.53.1"},"reference-count":11,"publisher":"Cambridge University Press (CUP)","license":[{"start":{"date-parts":[[2020,1,21]],"date-time":"2020-01-21T00:00:00Z","timestamp":1579564800000},"content-version":"unspecified","delay-in-days":20,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. Funct. Prog."],"published-print":{"date-parts":[[2020]]},"abstract":"<jats:p>\n                    The Garsia\u2013Wachs 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\u2013Wachs algorithm can be implemented with a\n                    <jats:italic>linearithmic<\/jats:italic>\n                    running time\u2014a running time of\n                    <jats:italic>O<\/jats:italic>\n                    (\n                    <jats:italic>n<\/jats:italic>\n                    log\n                    <jats:italic>n<\/jats:italic>\n                    ) steps for an input of length\n                    <jats:italic>n<\/jats:italic>\n                    , the same time bound as for Huffman coding.\n                  <\/jats:p>","DOI":"10.1017\/s0956796819000194","type":"journal-article","created":{"date-parts":[[2020,1,21]],"date-time":"2020-01-21T02:37:42Z","timestamp":1579574262000},"source":"Crossref","is-referenced-by-count":1,"title":["An optimal, purely functional implementation of the Garsia\u2013Wachs algorithm"],"prefix":"10.1017","volume":"30","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3901-742X","authenticated-orcid":false,"given":"RICHARD S.","family":"BIRD","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"56","published-online":{"date-parts":[[2020,1,21]]},"reference":[{"key":"S0956796819000194_ref4","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1959.tb01583.x"},{"key":"S0956796819000194_ref3","doi-asserted-by":"publisher","DOI":"10.1137\/0206045"},{"key":"S0956796819000194_ref2","doi-asserted-by":"publisher","DOI":"10.1145\/1411304.1411317"},{"key":"S0956796819000194_ref1","doi-asserted-by":"crossref","DOI":"10.1017\/9781108869041","volume-title":"Algorithm Design with Haskell","author":"Bird","year":"2020"},{"key":"S0956796819000194_ref11","volume-title":"The Art of Computer Programming, Volume 3: Sorting and Searching","author":"Knuth","year":"1998"},{"key":"S0956796819000194_ref6","doi-asserted-by":"publisher","DOI":"10.1137\/0121057"},{"key":"S0956796819000194_ref7","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796897002864"},{"key":"S0956796819000194_ref8","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(96)00296-4"},{"key":"S0956796819000194_ref5","volume-title":"Combinatorial Algorithms","author":"Hu","year":"1982"},{"key":"S0956796819000194_ref9","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(88)90009-0"},{"key":"S0956796819000194_ref10","doi-asserted-by":"publisher","DOI":"10.1007\/BF00264289"}],"container-title":["Journal of Functional Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0956796819000194","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,26]],"date-time":"2026-05-26T22:36:50Z","timestamp":1779835010000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0956796819000194\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"references-count":11,"alternative-id":["S0956796819000194"],"URL":"https:\/\/doi.org\/10.1017\/s0956796819000194","relation":{},"ISSN":["0956-7968","1469-7653"],"issn-type":[{"value":"0956-7968","type":"print"},{"value":"1469-7653","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020]]},"article-number":"e3"}}