Pairing heaps with O(log log n) decrease cost

Amr Elmasry

2009 · 18 citations · 7 references

Concepts

Abstract

We give a variation of the pairing heaps for which the time bounds for all the \noperations match the lower bound proved by Fredman for a family of similar \nself-adjusting heaps.\nNamely, our heap structure requires $O(1)$ for insert and find-min, \n$O(\\log{n})$ for delete-min, and $O(\\log\\log{n})$ for decrease-key and meld \n(all the bounds are in the amortized sense except for find-min).

References

7