Problem:
Keep track of the median when data arrives 1 by 1, compute the sum of all medians modulo 10000 for each element.
Solution:
I loved this idea in the lecture, we maintain two heaps. The low heap contains the smaller half of the integers and we enable extract max there. The high heap contains the bigger half of the integers and we enable extract min there. We can use constant number of heap operation to maintain the invariant and therefore the per data item cost is $ O(\log n) $.
Keep track of the median when data arrives 1 by 1, compute the sum of all medians modulo 10000 for each element.
Solution:
I loved this idea in the lecture, we maintain two heaps. The low heap contains the smaller half of the integers and we enable extract max there. The high heap contains the bigger half of the integers and we enable extract min there. We can use constant number of heap operation to maintain the invariant and therefore the per data item cost is $ O(\log n) $.
No comments:
Post a Comment