数据流中的中位数

使用2个堆,一个小顶堆一个大顶堆。保持大顶堆的最大元<=小顶堆的最小元，且元素个数小顶堆>=大顶堆但是至多相差1
这样如果有奇数个元素中位数就是小顶堆的最小元(堆顶)
在push的时候注意保持上面条件.另外注意处理空的情况

#include<string>
#include<stdio.h>
#include<queue>
#include<algorithm>

class two_heaps{
  public:
  std::priority_queue<int,std::vector<int>,std::greater<int>>min_heap;
  std::priority_queue<int>max_heap;
  //min_heap的最小元>=max_heap的最大元,元素个数min_heap>=max_heap且至多差1
  void push(int a){
    //首次push放入min_heap
    if(min_heap.size()==0){
      min_heap.push(a);
      return;
    }
    //第二次push
    else if(max_heap.size()==0){
      if(a>=min_heap.top()){
        max_heap.push(a);
        return;
      }
      else{
        max_heap.push(min_heap.top());
        min_heap.pop();
        min_heap.push(a);
      }
    }
    int max_element_in_min_heap=min_heap.top();
    int min_element_in_max_heap=max_heap.top();
    if(a<=max_element_in_min_heap){
      max_heap.push(max_element_in_min_heap);
      min_heap.pop();
      min_heap.push(a);
    }
    else if(a<=min_element_in_max_heap){
      if(min_heap.size()>max_heap.si***_heap.push(a);
      else max_heap.push(a);
    }
    else{
      min_heap.push(min_element_in_max_heap);
      max_heap.pop();
      max_heap.push(a);
    }
  }
  double get(){
    size_t total_si***_heap.size()+max_heap.size();
    if(total_size%2)return min_heap.top();
    else if(total_size==0)return 0;
    else return (min_heap.top()+max_heap.top())/2.0;
  }
};
int main() {
  two_heaps a;
  printf("%.2f\n",a.get());
  a.push(1);
  printf("%.2f\n",a.get());
  a.push(2);
  printf("%.2f\n",a.get());
  a.push(1);
  printf("%.2f\n",a.get());
  return 0;
}

priority_queue自定义comparator
我们知道可以对priority_queue<t>中的class T重载operator<
但是如果要用一个额外的comparator的形式,由于comparator是模板参数的一部分而不是构造函数的一部分,声明方式与Java不同
template<
class T,
class Container = std::vector<t>,
class Compare = std::less</t></t>

class priority_queue;

auto cmp=[](const int a,const int b){return b<a;};
std::priority_queue<int,std::vector<int>,decltype(cmp)>pq(cmp);
注意cmp必须同时作为构造函数参数传入否则报错如下
error: use of deleted function ‘<lambda(int, int)>::<lambda>()’
priority_queue(const _Compare& __x = _Compare()</lambda></int>

当我们没有将cmp传递给构造函数的时候，会试图调用decltype(cmp)这个类型的默认构造函数来构造一个与cmp类型相同的对象，但是lambda的默认构造函数是deleted所以报错