Design a data type that supports insert in logarithmic time, find-the-median in constant time, and remove-the-median in logarithmic time.
public double getMedian(leftset, rightSet, input) { //其中左边集合为比较小的元素集合，右边集合为大的元素集合
while((item = input.read()) != null) // 可以读取到元素{
if(item < leftSet.top) { // 如果小于左边集合
leftSet.insert(item);
} else {
rightSet.insert(item); //将元素加入到右边集合
}
// 判断两边元素个数的差异，进行调整
if(leftSet.size() - rightSet.size() == 2) { //如果左边元素集合比右边元素集合大2, 取顶元素加入到右边
item = leftSet.remove();
rightSet.insert(item);
}
// 同样应用于右边元素比左边元素大2的情况
if(rightSet.size() - leftSet.size() == 2) { //如果右边元素集合比左边元素集合大2, 取顶元素加入到左边
item = rightSet.remove();
leftSet.insert(item);
}
}
// 在元素取完之后要判断两边集合元素的情况
if(leftSet.size() == rightSet.size()) {
return (leftSet.top() + rightSet.top()) / 2;
} else if(leftSet.size() > rightSet.size()) {
return leftSet.top();
} else
return rightSet.top();
}
