1

I'm working on an assignment for one of my courses, and one question asks to show that the decrease-key operation, for a pairing heap, takes O(1) time.

Obviously, if you have a pointer to the key you want to decrease, then the operation will take O(1) time (just delete link, change key value, then merge).

However, no where in the assignment does it say that we are given a pointer to the key. If we're not given a pointer, then there is no way decrease-key would take O(1) time (you'd have to look for the key in the heap first, and this doesn't take constant time). I looked at literature, and all say that decrease key takes O(logn) time.

Am I missing something here?

Asool
  • 13,031
  • 7
  • 35
  • 49
  • No, you're not missing anything. If you don't have a reference to the node, then you'll have to do an O(n) pass to find it. – Jim Mischel Aug 08 '16 at 16:08

1 Answers1

2

The amortized cost of a decrease-key in a pairing heap is not O(1) even if you have a pointer to the element in question. It's been proven that there is an Ω(log log n) lower-bound on the amortized cost of a decrease-key operation in a pairing heap. This isn't easy to prove; see this paper for details.

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
  • That's odd because in original paper there is very simple operation which is completely local (it depends on 3 nodes max, no matter the size of the heap). However it is paid content :-(. I assume you've read it, can you at least tell which variant was analyzed -- one with (parent+left child + right sibling) pointers or one with (left sibling/parent pointer + right sibling), and if the decrease-key compared its value to the parent or not (in original, it didn't). – greenoldman Dec 22 '18 at 14:34
  • 1
    You’re correct that the worst-case runtime of a decrease-key is O(1). However, by performing a decrease-key operation the heap gets restructured in a way that then causes future delete-min operations to run more slowly. The amortized analysis of the pairing heap works by backcharging the work from the delete-min back to the preceding operations, and in doing so the *amortized* cost of the decrease-key is Omega(log log n). – templatetypedef Dec 22 '18 at 17:25