A TIGHT LOWER-BOUND FOR TOP-DOWN SKEW HEAPS

Previously, it was shown in a paper by Kaldewaij and Schoenmakers that for top-down skew heaps the amortized number of comparisons required for meld and delmin is upper bounded by log(phi) n, where n is the tot al size of the inputs to these operations and phi = (root 5 + 1)/2 den otes the golden ratio. In this paper we present worst-case sequences o f operations on top-down skew heaps in which each application of meld and delmin requires approximately log(phi) n comparisons. As the remai ning heap operations require no comparisons, it then follows that the set of bounds is tight. The result relies on a particular class of sel f-recreating binary trees, which is related to a sequence known as Hof stadter's G-sequence. (C) 1997 Elsevier Science B.V.