Find the Running Median

  • + 8 comments

    Hmmmm, I simply inserted each new number into an array in sorted order (as you would do in an insertion sort) and then used the array indexes to calculate the medians.

    My reasoning was that since a print had to be done after each insertion, it would take linear time to print each result.

    My maximum running time was 1.72 sec.

    Now that I have seen the hints on how the min and max heaps should be used, I guess I should do it properly and see how it affects the running time.

    EDIT: I have now re-written the solution using heaps as recommended. The maximum running time is now down to 0.06 sec.