# Priority Queues with $DecreaseKey,FindMin,Insert$ in time $O(1)$, $DeleteMin$ in $O(\log n)$ and $IncreaseKey$ in $O(1)$, Amortized

Problem:
In this problem, we discuss Data-Structures that maintain a group of ordered elements.
We must support the operations $$DecreaseKey, FindMin, Insert$$ in time $$O(1)$$ and the operation $$DeleteMin$$ in time $$O(\log n)$$. All the time-complexities are Amortized.
We'll remind that so far, Fibonacci Heaps answer the requirements of the Time-Complexity requirements.
Suppose that all elements that are kept in the data-structure are different.

Question:
Suppose that $$a$$ is an element that exists in the data-structure.
Denote its successor as $$Succ(a)$$ and its Successor's Successor as $$Succ(Succ(a))$$.
We'll want to add the operation $$IncreaseKey(a,d)$$ which adds $$d$$ to the value of key $$a$$ under the constraint that $$a \leq a+d < Succ(Succ(a))$$.
This means, the location of $$a$$ in the sorted sequence of the elements of the data-structure cannot go over one because of the operation.
In addition, we'll demand that $$a$$ is not the minimal element in the data-structure ( Note: It is promised to us that both of these conditions will hold when we call the operation ).
Is it possible to add the new operation ( $$IncreaseKey(a,d)$$ ) in time $$O(1)$$ amortized, given pointers to $$a , Succ(a)$$?

Attempt:
Not possible. Note that we need to maintain the pointer of a successive element under $$Insert$$ and $$Decrease-Key$$. Insert won't cost $$O(1)$$ amortized anymore since it is possible that when we insert a new element into the data-structure, it will be a successor of one of the elements in the data-structure. Hence, we'll need to go over all the elements in the tree in order to find the node whose pointer to a successor needs to be updated. The argument is similar for $$DecreaseKey$$. Hence, although $$IncreaseKey(a,d)$$ will run in $$O(1)$$ amortized, $$Insert,DecreaseKey$$ won't run in $$O(1)$$, hence such an operation cannot be added.

I know my attempt's specious since I don't explain why Insert costs $$O(1)$$ , also I'm not sure if I need to do amortized-analysis from scratch ( to justify the costs of all the operations under the addition of the new one ). I'm not sure what the answer is and I'll appreciate the help! Thanks in advance!

• What is your question? Jun 13, 2022 at 16:13
• It appears in Question, I've bolded it now, it can't be explained without background information first as I've written. Jun 13, 2022 at 17:16
• As you have already tried to answer your own question, you should be more precise in what you are asking: do you want a review of your answer? Do you think there is a problem with it? Do you want a more precise answer? Jun 13, 2022 at 17:23
• Well, its a question of understanding and I haven't encountered such questions in my studies of algorithmics that take a data-structure, add to it an operation under some constraints ( or remove an operation ) and then you're supposed to think about the operations amortized costs under the new givens and prove/disprove if such-and-such amortized-costs for some operation is possible under the new constraints ( note that this question is not necessarily about finding the amortized cost, but proving if it can be from a specific family of functions under different constraints ). Jun 13, 2022 at 17:43
• This is first time I'm encountering such question and I'm wondering how one would approach it, since this question can provide an example for solving such questions, I want a more precise answer that can explain whether or not $IncreaseKey(a,d)$ can be added in $O(1)$ Amortized, how can you prove it?. I can re-calculate the amortized costs from scratch of each operation, however, that won't provide prove and disprove. Jun 13, 2022 at 17:43