Divide-and-conquer recurrences associated with generalized heaps, optimal merge, and related structures
Resource
Theoretical Computer Science 292 (3): 667-677
Journal
Theoretical Computer Science
Pages
667-677
Date Issued
2003
Date
2003
Author(s)
Chen, Wei-Mei
Abstract
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.
Subjects
Divide-and-conquer; Generalized heap; Huffman coding; Optimal merge
Other Subjects
Algorithms; Combinatorial mathematics; Encoding (symbols); Probability; Huffman coding; Computer science
Type
journal article
File(s)![Thumbnail Image]()
Loading...
Name
41.pdf
Size
143.8 KB
Format
Adobe PDF
Checksum
(MD5):fada885e0100b396a79fbe7b94f4b774