A tight lower bound for top-down skew heaps

    Research output: Contribution to journalArticleAcademicpeer-review

    2 Citations (Scopus)


    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.
    Original languageEnglish
    Pages (from-to)279-284
    JournalInformation Processing Letters
    Issue number5
    Publication statusPublished - 1997


    Dive into the research topics of 'A tight lower bound for top-down skew heaps'. Together they form a unique fingerprint.

    Cite this