Skip to content

Instantly share code, notes, and snippets.

@ktraff
Created April 6, 2013 21:36
Show Gist options
  • Save ktraff/5327721 to your computer and use it in GitHub Desktop.
Save ktraff/5327721 to your computer and use it in GitHub Desktop.
maintain the median with heaps 4
public double getMedian() {
int size = minHeap.size() + maxHeap.size();
double median = Integer.MAX_VALUE;
if(size % 2 == 0)
{
if(!minHeap.peek()) median = maxHeap.peek();
else if(!maxHeap.peek()) median = minHeap.peek();
else median = ((double) minHeap.peek() + maxHeap.peek()) / 2;
}
else
{
median = (maxHeap.size() >= minHeap.size()) ? maxHeap.peek() : minHeap.peek();
}
return median;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment