Abstract | ||
---|---|---|
Previously, it was shown in a paper by Kaldewaij and Schoenmakers that for topdownskew heaps the amortized number of comparisons required for meld and delmin isupper bounded by log OE n, where n is the total size of the inputs to these operations andOE = (p5+1)=2 denotes the golden ratio. In this paper we present worst-case sequences ofoperations on top-down skew heaps in which each application of meld and delmin requiresapproximately log OE n comparisons. As the remaining heap... |
Year | DOI | Venue |
---|---|---|
1997 | 10.1016/S0020-0190(97)00028-8 | Inf. Process. Lett. |
Keywords | Field | DocType |
top-down skew heap,priority queue,top down,golden ratio,data structure,lower bound,amortized complexity,analysis of algorithms | Discrete mathematics,Combinatorics,Skew heap,Upper and lower bounds,Analysis of algorithms,Amortized analysis,Binary tree,Heap (data structure),Skew,Mathematics,Bounded function | Journal |
Volume | Issue | ISSN |
61 | 5 | 0020-0190 |
Citations | PageRank | References |
1 | 0.34 | 8 |
Authors | ||
1 |
Name | Order | Citations | PageRank |
---|---|---|---|
Berry Schoenmakers | 1 | 1550 | 119.18 |