A method for fast median filtering in an implantable medical device is disclosed
that provides rapid filtering using computational mechanisms with following elements.
A new sample value is received into a buffer. An oldest sample value location is
identified in a MIN-heap and a MAX-heap. A new sample value location is identified
in either the MIN-heap or the MAX-heap by comparing the new sample value to a median
value. The new sample value is placed into the oldest sample value location, if
the MIN-heap or MAX-heap identified for the new sample value location is the same
as the MIN-heap or MAX-heap identified for the oldest sample value location. A
MIN-heap top or MAX-heap top is moved from the heap not containing the oldest value
into the location of the oldest sample and the new sample is placed into the location
of the MIN-heap top or MAX-heap top moved from the heap not containing the oldest
value, if the heap identified for the new sample is not the same as the heap identified
for the oldest sample. The MAX-heap is rebalanced so the MAX-heap top contains
the highest value in the MAX-heap and the MIN-heap is rebalanced so the MIN-heap
top contains the lowest value in the MIN-heap. The median value is calculated by
averaging the MIN-heap top plus the MAX-heap top. The method for fast median filtering
in an implantable medical device can also be expressed as a computer software product
that includes a medium readable by a processor.