# 力扣- 剑指 Offer 41题 数据流中的中位数（C++）- 大顶堆、小顶堆

``````class MedianFinder {

public:
/** initialize your data structure here. */
MedianFinder() {

}

//目的：minheap中放较大的元素，堆顶为最小的元素；maxheap中放较小的元素，堆顶为最大的元素
//如果是奇数：大顶堆元素数-小顶堆元素数=1
//如果是偶数：大顶堆元素数=小顶堆元素数
if(maxheap.size()==0||num<maxheap.top()) maxheap.push(num);
else minheap.push(num);

while(maxheap.size()<minheap.size()){
//小顶堆元素放到大顶堆
int temp=minheap.top();
minheap.pop();
maxheap.push(temp);
}

while(minheap.size()<maxheap.size()-1){
//大顶堆元素放到小顶堆
int temp=maxheap.top();
maxheap.pop();
minheap.push(temp);
}
}

double findMedian() {

if(maxheap.size()>minheap.size()) return maxheap.top();
else return (maxheap.top()+minheap.top())/2.0;
}
private:
priority_queue<int> maxheap;//放较小的元素
priority_queue<int,vector<int>,greater<int>> minheap;//放较大的元素
};

/** * Your MedianFinder object will be instantiated and called as such: * MedianFinder* obj = new MedianFinder(); * obj->addNum(num); * double param_2 = obj->findMedian(); */
``````

https://blog.csdn.net/qq_40467670/article/details/126179313

Scroll to Top