# Modify max value multiple times of a list

I have two lists say $$A$$ and $$B$$, each consisting of n positive integers. I make a list $$C$$ such that each element of $$C$$ i.e., $$C_i=A_iB_i$$ for each element $$A_i \in A$$ and $$B_i \in B$$.

Now I have to update the value of the maximum element of $$C$$ say $$C_j$$ by decreasing $$B_j$$ such that $$B_j \geq 0$$ and $$C_j$$'s updated value should be less than the second maximum element of $$C$$.

The above operation have to be applied $$m$$-times.

The approach I used was:

• Build a Max Heap of list C
• repeat $$m$$-times
• update the value of max element of heap according to the given condition
• Apply Max-Heapify

The above approach worked fine. So my question is "Is there any way to do the above task in a faster way than my approach?"

• is there a chance that an element of C is updated more than once? – kelalaka Oct 19 '18 at 11:22
• Yes there sure is – Sc00by_d00 Oct 19 '18 at 11:50
• is there a max size of the integers? – kelalaka Oct 19 '18 at 11:51
• 10^9 for each element of A and B – Sc00by_d00 Oct 19 '18 at 11:53
• can we think that the numbers are distributed randomly in the range $1 \leq \leq 10^9$ – kelalaka Oct 20 '18 at 22:52

• In the binary heaps, Decrease_Key is $$\mathcal{O}(\log n)$$ cost in the worst case. If you use Fibonacci heaps1, Decrease_Key is $$\mathcal{\Theta(1)}$$ in amortized time. With the binary heaps, you will have $$\mathcal{O}(m \log n)$$ whereas in Fibonacci heaps you will have $$\mathcal{\theta(m)}$$ in amortized time.