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?
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.