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?"
One solution is changing the underlying data structure;


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.




note : Fibonacci Heaps are theoretically better than Binary Heaps. But their the constant factors hidden are very high.



1 Introduction To Algorithms 3rd. Ed. Cormen et. al. at section 19.