find the median in a fix-sized moving window on a long sequency of data

[nuzzle]

My second suggestion is to replace the binary search trees with fibonacci heaps, a max-heap for the left partition and a min-heap for the right.

It looks like this suggestion actually is patented.

http://www.google.com.tw/patents/about?id=kQwWAAAAEBAJ

It's not that surprising really because median filtering is an important way to reduce random "salt and pepper" noise.

Spontaneously I find it quite annoying that it's possible to patent things like this. But fortunately the patent is somewhat limited in scope to "implantable medical device". Also using other kinds of heaps (such as fibonacci) doesn't seem to infringe on this particular patent because it's clearly limited to binary heaps.

Also it seems limited to finding the median in O(log N) where N is the sliding window size. So if someone actually comes up with an O(1) solution it most likely has substantial commersial value and it would be a good idea to first file for a patent before posting it here. And then make a killing by letting Medtronic and their worst competitors fight for exclusive rights.