配列の中央値を動的に探します.
783 ワード
中央値を探している間に、二叉の山を二つ使って実現できます.一番大きい山と一番小さい山を二つ使って、二つのtopを演算します.具体的にコードを参照:
void addnum(int num)
{
if(big_queue.empty()){
big_queue.push(num);
}
if(big_queue.size()==small_queue.size()) // 2 ，
{
if(num>big_queue.top())
small_queue.push(num);
else
big_queue.push(num);
}
else if(big_queue.size()>small_queue.size())
{
if(num>big_queue.top())
small_queue.push(num);
else{
small_queue.push(big_queue.top());
big_queue.pop();
big_queue.push(num);
}
}
else if(big_queue.size()small_queue.size())
return big_queue.top();
else
return small_queue.top();
}