Patent ID: 6941332

Claim:
A method for median filtering in an implantable medical device, comprising: receiving a new sample value into a buffer; identifying an oldest sample value location in a MIN-heap and a MAX-heap; identifying a new sample value location in either the MIN-heap or the MAX-heap by comparing the new sample value to a median value; placing the new sample value 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; moving a MIN-heap top or MAX-heap top from the heap not containing the oldest value into the location of the oldest sample and placing the new sample 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; rebalancing the MAX-heap so the MAX-heap top contains the highest value in the MAX-heap and rebalancing the MIN-heap so the MIN-heap top contains the lowest value in the MIN-heap; and, calculating the median value by averaging the MIN-heap top plus the MAX-heap top.