左边大顶堆,右边小顶堆。右边数量比左边多一,左边放小的那半数,右边放大的那半
是偶数个,那就返回两个根堆的头结点的q平均值,如果是奇数,就是小根堆的数量大于大根堆数量1个,返回小根堆的头;
当左右平等数量的时候,往小根堆了加入,当小根堆大于大根堆时候,往大根堆里加入
1 priority_queue<int> big; 2 priority_queue<int,vector<int>,greater<int> > small; 3 void addNum(int num){//左边大顶堆(根节点最大),右边小顶堆(根节点最小),左边放较小数,右边放较大数,保证右边数量比左边大一,所以最开始应向右边堆放入数据,奇数时返回小顶堆根节点,偶数时返回两堆根节点平均值 4 //数据放入:当右边堆为空时,首先放入右边; 5 //当右边不为空左边为空,将较小的放入左边------首先将数据放入右边,再将较小数放入左边 6 if(small.empty()) small.push(num); 7 else if(big.empty(){ 8 small.push(num); 9 big.push(small.top()); 10 small.pop(); 11 } 12 //当两个堆不为空 13 else{ 14 if(big.size()==small.size())//当两个堆数量相同,将数据放入大顶堆,将最大的数放入小顶堆 15 { 16 big.push(num); 17 small.push(big.top()); 18 big.pop(); 19 } 20 else{//将数据放入小顶堆,将其中最小数放入左边堆 21 small.push(num); 22 big.push(small.top()); 23 small.pop(); 24 } 25 } 26 } 27 double findMedian) { 28 if(big.empty()&&small.empty()) return 0; 29 else if(big.size() == small.size()){ 30 double p1 = big.top(); 31 double p2 = small.top(); 32 return (p1+p2)/2; 33 } 34 else return small.top(); 35 }