maintain_median.cpp

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
inline bool comparator(const int &a, const int &b)
{
    return a < b;
}
int maintain(vector<int> &v)
{
    //use simplified name!! next time!
    
    vector<int> max_heap; //for smaller number
    vector<int> min_heap;
    make_heap(max_head.begin(), max_heap.begin());
    make_heap(min_head.begin(), min_heap.begin(), comparator();
    for (int i = 0; i < v.size(); i++) {
        //either equal
        if (max_heap.size() == min_heap.size()) {
            if (!min_heap.empty() && v[i] > min_heap[0]) {
                max_heap.push_back(min_heap[0]);
                push_heap(max_heap.begin(), max_heap.end());
                
                pop_heap(min_heap.begin(), min_heap.end());
                min_heap.pop_back();
                
                min_heap.push_back(v[i]);
                push_heap(min_heap.begin(), min_heap.end());
            }
            else {
                max_heap.push_back(v[i]);
                push_heap(max_heap.begin(), max_heap.end());
            }

        }
        //or larger
        else {
            if (v[i] < max_heap[0]) {
                
            }
            else {
                //add into
            }

        }
    }

    if (max_heap.size() > min_heap.size()) return max_heap[0];
    else return (max_heap[0] + min_heap[0]) / 2;
}
int main()
{
    int a[] = {1, 2, 3, 4, 5};
    vector<int> v(a, a+5);
    
    return 0;
}