Improved upper bounds for pairing heaps

John Iacono

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Abstract

    Pairing heaps are shown to have constant amortized time in-sert and zero amortized time meld, thus improving the previous O(log n) amortized time bound on these operations. It is also shown that pairing heaps have a distribution sensitive behavior whereby the cost to per-form an extract-min on an element x is O(log min(n; k)) where k is the number of heap operations performed since x's insertion. Fredman has observed that pairing heaps can be used to merge sorted lists of varying sized optimally, within constant factors. Utilizing the distribution sensi-tive behavior of pairing heap, an alternative method the employs pairing heaps for optimal list merging is derived.

    Original languageEnglish (US)
    Title of host publicationAlgorithm Theory - SWAT 2000 - 7th Scandinavian Workshop on Algorithm Theory, 2000, Proceedings
    EditorsMagnús M. Halldórsson
    PublisherSpringer Verlag
    Pages32-45
    Number of pages14
    ISBN (Print)3540676902, 9783540676904
    DOIs
    StatePublished - 2000
    Event7th Scandinavian Workshop on Algorithm Theory, SWAT 2000 - Bergen, Norway
    Duration: Jul 5 2000Jul 7 2000

    Publication series

    NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    Volume1851
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349

    Other

    Other7th Scandinavian Workshop on Algorithm Theory, SWAT 2000
    CountryNorway
    CityBergen
    Period7/5/007/7/00

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Computer Science(all)

    Fingerprint Dive into the research topics of 'Improved upper bounds for pairing heaps'. Together they form a unique fingerprint.

    Cite this