Chen, Wei-MeiWei-MeiChenChen, Gen-HueyGen-HueyChen2009-04-292018-07-052009-04-292018-07-052003https://www.scopus.com/inward/record.uri?eid=2-s2.0-0037473921&doi=10.1016%2fS0304-3975%2801%2900336-X&partnerID=40&md5=b5d343588256c082c823a9be8bb73d7cAn elementary approach is given to studying the recurrence relations associated with generalized heaps (or d-heaps), cost of optimal merge, and generalized divide-and-conquer minimization problems. We derive exact formulae for the solutions of all such recurrences and give some applications. In particular, we present a precise probabilistic analysis of Floyd's algorithm for constructing d-heaps when the input is randomly given. A variant of d-heap having some interesting combinatorial properties is also introduced. © 2002 Elsevier Science B.V. All rights reserved.application/pdf147251 bytesapplication/pdfen-USDivide-and-conquer; Generalized heap; Huffman coding; Optimal mergeAlgorithms; Combinatorial mathematics; Encoding (symbols); Probability; Huffman coding; Computer sciencejournal article10.1016/S0304-3975(01)00336-X2-s2.0-0037473921http://ntur.lib.ntu.edu.tw/bitstream/246246/154726/1/41.pdf