Find running median from a stream of integers

Re:Find running median from a stream of integers by sixothree on Monday May 21, 2012 @05:50PM (#4005105)

Heap sounds like overkill to find the middle value in a running list. What's wrong with simple stack and keeping track of how many integers you've received?

[ Parent | on HN ]

Re:Find running median from a stream of integers by xyzzyz on Monday May 21, 2012 @07:05PM (#4005347)

What's wrong with simple stack and keeping track of how many integers you've received?

I'm sorry, but I have absolutely no idea what you are talking about. Perhaps you could describe your solution a bit more.

[ Parent | on HN ]

Re:Find running median from a stream of integers by jbritto on Monday May 21, 2012 @05:54PM (#4005118)

I'm not sure what you have in mind (perhaps finding the mean? but why the stack?) but that would not work for median.

[ Parent | on HN ]

Re:Find running median from a stream of integers by Drbble on Monday May 21, 2012 @11:21PM (#4006126)

Your solution is for median position, not median value, and it would require a queue, not a stack, so unneeded old values could be dropped.

[ Parent | on HN ]

Re:Find running median from a stream of integers by sixothree on Tuesday May 29, 2012 @05:15PM (#4039958)

Of course, a queue is correct.

[ Parent | on HN ]