Pairing Heaps with Costless Meld

Details Pairing Heaps with Costless Meld Pairing Heaps with Costless Meld

2009-03-24

arxiv.org/abs/0903.4130v2

Computer Science

Data Structures and Algorithms

10 pages, 2 figures

Scientific paper

Improving the structure and analysis in \cite{elm0}, we give a variation of the pairing heaps that has amortized zero cost per meld (compared to an $O(\log \log{n})$ in \cite{elm0}) and the same amortized bounds for all other operations. More precisely, the new pairing heap requires: no cost per meld, O(1) per find-min and insert, $O(\log{n})$ per delete-min, and $O(\log\log{n})$ per decrease-key. These bounds are the best known for any self-adjusting heap, and match the lower bound proved by Fredman for a family of such heaps. Moreover, the changes we have done make our structure even simpler than that in \cite{elm0}.

Affiliated with

Also associated with

No associations

Rating

Pairing Heaps with Costless Meld does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Pairing Heaps with Costless Meld, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Pairing Heaps with Costless Meld will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-348283