ANALYSIS OF A CLASS OF MERGESORTS AND RELATED STRUCTURES
| Autor: | Chen, Wei-Mei, 陳維美 |
|---|---|
| Rok vydání: | 2000 |
| Druh dokumentu: | 學位論文 ; thesis |
| Popis: | 88 We study in detail in this thesis the stochastic behaviors of a class of mergesorts and some closely related data structures. First we give a complete analysis of the cost distribution of queue-mergesort (known previously as an optimal variant of mergesorts in the worst case) based on Huffman coding of identical weights, including the best, average and variance cases. The asymptotic normality of its cost is also established under the uniform permutation model. A comparative discussion is then given on the probabilistic behaviors of top-down mergesort, bottom-up mergesort and queue-mergesort. The detailed comparison naturally leads to the study of the corresponding optimality problems for which we identify optimal mergesorts in the average and variance cases. We also examine further combinatorial and algorithmic properties of general power-of-2 rules of which the underlying dividing rule of queue-mergesort is a special case. Inspired by the close relationship between heap and queue mergesort, we consider extensions of these problems to higher orders (or dimensions) in two different lines of the generalization based on heap structures and multiway merge, respectively. We prove that the optimal $d$-way merge tree and $d$-heap structure have essentially the same shape. Besides, we study the exact solutions of the recurrences associated with generalized heap (or $d$-heap), optimal merge, and generalized divide-and-conquer minimization problem, by a unified and elementary approach. As applications of the exact solutions, we present a precise probabilistic analysis of Floyd''s algorithm for constructing $d$-heaps. Finally we propose a variant of $d$-heap (called $d^*$-heap) having some interesting combinatorial properties. |
| Databáze: | Networked Digital Library of Theses & Dissertations |
| Externí odkaz: |
|