<p>The <strong>median</strong> is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle values.</p>

<ul>
	<li>For examples, if <code>arr = [2,<u>3</u>,4]</code>, the median is <code>3</code>.</li>
	<li>For examples, if <code>arr = [1,<u>2,3</u>,4]</code>, the median is <code>(2 + 3) / 2 = 2.5</code>.</li>
</ul>

<p>You are given an integer array <code>nums</code> and an integer <code>k</code>. There is a sliding window of size <code>k</code> which is moving from the very left of the array to the very right. You can only see the <code>k</code> numbers in the window. Each time the sliding window moves right by one position.</p>

<p>Return <em>the median array for each window in the original array</em>. Answers within <code>10<sup>-5</sup></code> of the actual value will be accepted.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,3,-1,-3,5,3,6,7], k = 3
<strong>Output:</strong> [1.00000,-1.00000,-1.00000,3.00000,5.00000,6.00000]
<strong>Explanation:</strong> 
Window position                Median
---------------                -----
[<strong>1  3  -1</strong>] -3  5  3  6  7        1
 1 [<strong>3  -1  -3</strong>] 5  3  6  7       -1
 1  3 [<strong>-1  -3  5</strong>] 3  6  7       -1
 1  3  -1 [<strong>-3  5  3</strong>] 6  7        3
 1  3  -1  -3 [<strong>5  3  6</strong>] 7        5
 1  3  -1  -3  5 [<strong>3  6  7</strong>]       6
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,2,3,4,2,3,1,4,2], k = 3
<strong>Output:</strong> [2.00000,3.00000,3.00000,3.00000,2.00000,3.00000,2.00000]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= k &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>-2<sup>31</sup> &lt;= nums[i] &lt;= 2<sup>31</sup> - 1</code></li>
</ul>

//5:48
/*
1,3,-1,-3,5,3,6,7

1,3,-1,-3

-3,-1,1,3

3,1

-1,-3

greater k/2 min and smaller k/2 max ka average is our answer

take first k elements
sort them,
put first k/2 in a max heap
and last k/2 in a min heap

3,-1,-3,5
-3,-1,3,5



1,3,-1,-3,5,3,6,7
1,3,-1,-3

-3,-1,1,3

pop out 1

all elements of minh > all elements of maxh

-3,-1   3
new element is 5
if 5 > maxh.top then push 5 in min heap
if 5 < maxh.top then push 5 in max h

now if heaps are unbalanced, then pop from larger and push in smaller
get median same way

if it was odd

-3 -1 3

-3 is gone, push middle value to that heap
now again same



let's say I can pop out if it is a node structure
where to put the new one in?

if k is odd
-1,1,3

-1
center chap will always be the median
3


-1,1,3: 1
-3,-1,3: -1

k is even or k is odd

if k is odd

brute force is every time sort the k elements
k can go to 1e5, klogk = 1e7 * n = 1e5 - will not pass

since we can have n-k traversals - n log k will work

1,3,-1 sorted

remove 1 and add -3

what about two heaps? 

if k is even

have a max heap of k/2
min heap of k/2





*/

class Solution {
private:
    typedef pair<int,int> pii;
    class mapheap {
    private:
        map<int,int> hm;
        int nsize;
        bool ismaxheap;
    public:
        mapheap(vector<int> &vals, bool ismaxheap = false) {
            nsize = vals.size();
            this->ismaxheap = ismaxheap;
            for (int val: vals) hm[val]++;
        }
        int size() {
            return nsize;
        }
        int top() {
            if (!hm.size()) return INT_MAX;
            if (ismaxheap) 
                return hm.rbegin()->first;
            else
                return hm.begin()->first;
        }
        void pop() {
            if (!hm.size()) return;
            if (ismaxheap) {
                auto it = hm.rbegin();
                it->second--;
                nsize--;
                if (!it->second) hm.erase(it->first);
            }
            else {
                auto it = hm.begin();
                it->second--;
                nsize--;
                if (!it->second) hm.erase(it->first);
            }
        }
        void push(int val) {
            hm[val]++; nsize++;
        }
        bool isPresent(int val) {
            return hm.count(val);
        }
        void remove(int val) {
            if (!hm.count(val)) return;
            hm[val]--;
            nsize--;
            if (!hm[val]) hm.erase(val);
        }
    };
    void removefromPQ(int val, mapheap *pq, int k, int center) {
        pq->remove(val);
        if (k & 1) pq->push(center);
    }
    void removePrev(int val, mapheap *pqMax, mapheap *pqMin, int k, int center) {
        if (pqMax->isPresent(val))
            removefromPQ(val, pqMax, k, center);
        else if (pqMin->isPresent(val))
            removefromPQ(val, pqMin, k, center);
    }
    
    void addNew(int val, mapheap *pqMax, mapheap *pqMin, int k, int center) {
        if (val <= pqMax->top())
            pqMax->push(val);
        else
            pqMin->push(val);
    }

    void shuffleheaps(mapheap *larger,mapheap *smaller,int k,int &center) {
        while (larger->size() > smaller->size()) {
            if (k & 1)
                center = larger->top();
            else
                smaller->push(larger->top());
            larger->pop();
        }
    }
    vector<double> k1case(vector<int>& nums) {
        int n = nums.size();
        vector<double> rv;
        for (int i = 0; i < n; i++) {
            rv.push_back(nums[i]);
        }
        return rv;
    }
    vector<double> k2case(vector<int>& nums) {
        int n = nums.size();
        vector<double> rv;
        double sum = 0;
        sum = (double) nums[0] + (double) nums[1];
        rv.push_back(sum/2);

        for (int i = 1; i < n-1; i++) {
            sum -= nums[i-1];
            sum += nums[i+1];
            rv.push_back(sum/2);
        }
        return rv;
    }
public:
    vector<double> medianSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        if (k == 1) return k1case(nums);
        if (k == 2) return k2case(nums);
        vector<int> firstk;
        for (int i = 0; i < k; i++) {
            firstk.push_back(nums[i]);
        }
        sort(firstk.begin(), firstk.end());
        vector<int> vfirst, vsecond;
        for (int i = 0; i < k/2; i++) {
            vfirst.push_back(firstk[i]);
            vsecond.push_back(firstk[k-1-i]);
        } 
        mapheap* pqMax = new mapheap(vfirst, true);
        mapheap* pqMin = new mapheap(vsecond, false);
        int center = 0;
        if (k & 1) center = firstk[k/2];
        int s = 0, e = k-1;
        vector<double> rv;
        while (e < n) {
            double median;
            if (k & 1) {
                median = center;
            }
            else {
                median = (double) pqMax->top() + (double) pqMin->top();
                median /= 2;
            }
            rv.push_back(median);
            removePrev(nums[s], pqMax, pqMin, k, center);
            s++;
            e++;
            if (e >= n) break;
            addNew(nums[e],pqMax, pqMin, k, center);
            if (pqMax->size() < pqMin->size())
                shuffleheaps(pqMin, pqMax, k, center);
            else
                shuffleheaps(pqMax, pqMin, k, center);

            //cout << "\ns = " << s << "; ismaxlarger = " << ismaxlarger << "; maxh size = " << maxh.size() << "; minh.size = " << minh.size();
            //remove nums[s] from the applicable heap
            //if k is even, put center in the same heap
            //add nums[e] to the applicable heap
            //if k is even then pop element from the larger size heap to center
            //if k is odd then resize heaps until both become similar
        }
        return rv;
        
    }
};
49270