Modify max value multiple times of a list
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.