Day7-线性表-堆-寻找中位数

//
// Created by renyi on 2019-06-10.
//
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

class FindMedian{
public:
    FindMedian(){//核心思想：每次插入后，最大堆堆顶，必须要小于最小堆堆顶，且插入前后，最大堆，最小堆元素个数差，要<=1
    }
    void addNum(int num){//因为最大堆元素整体小于最小堆，所以进来的第一个元素先插入最大堆
        if (more_heap.empty()){//若最大堆元素是空，即这是插第一个元素
            more_heap.push(num);//插入最大堆，然后返回，再插就走下面逻辑了
            return;
        }

        if (more_heap.size() == less_heap.size()){//当最大堆，最小堆元素个数一样时
            if (num < more_heap.top()){//当num小于最大堆堆顶时，即第一种情况
                more_heap.push(num);//直接插入最大堆
            } else{
                less_heap.push(num);//直接插入最小堆
            }
        }

        else if (more_heap.size() > less_heap.size()){//最大堆元素个数，大于最小堆元素个数
            if (num > more_heap.top()){//对应第二种情况
                less_heap.push(num);
            } else{
                less_heap.push(more_heap.top());
                more_heap.pop();
                more_heap.push(num);
            }
        }

        else if (more_heap.size() < less_heap.size()){//对应第三种情况
            if (num < less_heap.top()){
                more_heap.push(num);
            } else{
                more_heap.push(less_heap.top());
                less_heap.pop();
                less_heap.push(num);
            }
        }
    }

    double findMedian(){
        if (more_heap.size() == less_heap.size()){//当元素个数相同时，总数为偶数，中位数为中间两个数的平均数
            return (more_heap.top() + less_heap.top()) / 2;
        } else if (more_heap.size() > less_heap.size()){
            return more_heap.top();//当两者元素个数不一样，必定是奇+偶，是奇
        } else{//总数奇数个，取中间的即可
            return less_heap.top();//那么最大堆，最小堆，谁元素更多，谁的堆顶就是中间的数了
        }
    }

private:
    priority_queue<double> more_heap;//初始化一个最大堆
    priority_queue<double, vector<double>, greater<double> > less_heap;//初始化一个最小堆
};

int main(){
    FindMedian findMedian;
    int nums[] = {6, 10, 1, 7, 99, 4, 33};
    for (int i = 0; i < 7; ++i) {
        findMedian.addNum(nums[i]);
        printf("此时的中位数为:%.1f\n", findMedian.findMedian());
    }
    return 0;
}