https://scholars.lib.ntu.edu.tw/handle/123456789/118058
標題: | Divide-and-conquer recurrences associated with generalized heaps, optimal merge, and related structures | 作者: | Chen, Wei-Mei Chen, Gen-Huey |
關鍵字: | Divide-and-conquer; Generalized heap; Huffman coding; Optimal merge | 公開日期: | 2003 | 起(迄)頁: | 667-677 | 來源出版物: | Theoretical Computer Science | 摘要: | An 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. |
URI: | https://www.scopus.com/inward/record.uri?eid=2-s2.0-0037473921&doi=10.1016%2fS0304-3975%2801%2900336-X&partnerID=40&md5=b5d343588256c082c823a9be8bb73d7c | DOI: | 10.1016/S0304-3975(01)00336-X | SDG/關鍵字: | Algorithms; Combinatorial mathematics; Encoding (symbols); Probability; Huffman coding; Computer science |
顯示於: | 資訊工程學系 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。