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?"

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

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.