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 logf n, where n is the total size of the inputs to these operations and f = (v5 + 1)/2 denotes the golden ratio. In this paper we present worst-case sequences of operations on top-down skew heaps in which each application of meld and delmin requires approximately logf n comparisons. As the remaining heap operations require no comparisons, it then follows that the set of bounds is tight. The result relies on a particular class of self-recreating binary trees, which is related to a sequence known as Hofstadter's G-sequence.