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.

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) $?

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!

  • $\begingroup$ What is your question? $\endgroup$
    – Nathaniel
    Jun 13, 2022 at 16:13
  • $\begingroup$ It appears in Question, I've bolded it now, it can't be explained without background information first as I've written. $\endgroup$
    – flamel12
    Jun 13, 2022 at 17:16
  • $\begingroup$ 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? $\endgroup$
    – Nathaniel
    Jun 13, 2022 at 17:23
  • $\begingroup$ 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 ). $\endgroup$
    – flamel12
    Jun 13, 2022 at 17:43
  • $\begingroup$ 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. $\endgroup$
    – flamel12
    Jun 13, 2022 at 17:43


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.