深知身在情长在
怅望江头江水声
C++，最大堆，最小堆。
一开始想到的是直接用一个数组或者vector存储，插入的时候顺序查找并计数，然后Insert是O(n)，GetMedian是O(1)，但是觉得太简单了，肯定不是这样的，慢慢就想到能不能一半大，一半小，于是就想到了堆。
在插入的时候，把大的一半放到最小堆，把大的一半放到最大堆，而插入堆的复杂度是O(logn)，应该就欧科了。当然插入元素X的操作需要遵循以下规则：
- 如果两个堆都为空，将X插入最大堆
- 如果两个堆元素个数相等，分以下两种情况：
- 如果元素X大于最小堆的堆顶，则弹出最小堆堆顶，将堆顶元素插入最大堆，将元素X插入最小堆
- 否则直接将X插入最大堆
- 如果两个堆元素不等，则最大堆一定多一个元素：
- 如果元素X小于最大堆的堆顶，则弹出最大堆堆顶，将堆顶元素插入最小堆，将元素X插入最大堆
- 否则直接将X插入最小堆
GetMedian操作直接判断奇偶就哦科了！
class Solution {
public:
void pushh(vector<int> &heap, int num, int flag) {
heap.push_back(num);
if (flag == 1) // 小顶堆
push_heap(heap.begin(), heap.end(), less<int>());
else
push_heap(heap.begin(), heap.end(), greater<int>());
}
int poph(vector<int> &heap, int flag) {
if (flag == 1)
pop_heap(heap.begin(), heap.end(), less<int>());
else
pop_heap(heap.begin(), heap.end(), greater<int>());
int rnum = heap.back();
heap.pop_back();
return rnum;
}
void Insert(int num) {
if (max_heap.size() == min_heap.size()) {
if (max_heap.empty() || num < max_heap.front())
pushh(max_heap, num, 1);
else {
if (min_heap.front() < num) {
int pop_num = poph(min_heap, -1);
pushh(max_heap, pop_num, 1);
pushh(min_heap, num, -1);
} else
pushh(max_heap, num, 1);
}
} else {
if (num < max_heap.front()) {
int pop_num = poph(max_heap, 1);
pushh(max_heap, num, 1);
pushh(min_heap, pop_num, -1);
} else
pushh(min_heap, num, -1);
}
}
double GetMedian() {
if (min_heap.size() == max_heap.size())
return static_cast<double>(min_heap.front() + max_heap.front()) / 2.0;
else
return static_cast<double>(max_heap.front());
}
private:
vector<int> max_heap;
vector<int> min_heap;
};
