C++ Balance 3 Multisets/Heaps
Have 3 multisets: first multiset, middle multiset, last multiset.\n\nWe can limit the elements under consideration to  \'m\'. Because we are always interested i
Have 3 multisets: f*irst multiset, middle multiset, last multiset.*\n\nWe can limit the elements under consideration to  \'m\'. Because we are always interested in last m elements from the numbers stream. \nThe first multiset will contain first K smallest elements. and the last multiset will contain last K elements. \nThe middle multiset will contain *m - 2K* elements. (i.e we don\'t have to remove K smaller element and K larger elements from the stream to calculate average ).\n\nIf less than  \'m\' elements are processed in the number stream, the average will always be -1.\nSo we arrive at the following property which we will keep satisfying when more than \'m\' elemens are processed. \n**Property 1: At any given point, first.size() + middle.size() + last.size() should be equal to m**\n\nAlso have a queue or a vector to track the last element which is to be removed. \nWhen less than m elements are processed, push the element to the queue as well as to the middle multiset. \n\nWhen exactly m elemens are processed, then relalace the multisets in the following manner.\n\tAdd the first k elements from the middle multiset to the first multiset. \n\tAdd the last k elements form the middle multiset to the last multiset. \n\t\n```\n\t    int count = 0;\n\t\twhile(count < k)\n\t\t{\n\t\t\tfirst.insert(*middle.begin());\n\t\t\tmiddle.erase(middle.begin());\n\n\t\t\tlast.insert(*middle.rbegin());\n\t\t\tmiddle.erase(prev(middle.end()));\n\t\t\tcount++;\n\t\t}\n```\n\nNow all the multisets are balanced, When a new element is encountered, \nFirst add the element to the middle multiset.  \nWe also need to remove the first element from the queue and from one of the multisets (we need to look for the multisets one by one where the element exists) to satisfy **property 1** \nFind the multiset where the element exists and , then -\tRemove the element from the multiset and Adjust the multisets. \n\nAdjusting the multisets:\n*Both the first multiset and last multiset should have K elements.*\n\nif first multiset is having less than K elements, then adjust with middle multiset, so that first multiset will have K elements. \nif last multiset is haveing less than K elements, then adjust with middle multiset, so that last multiset will have K elements.\n```\nwhile(first.size() < k)\n{\n\tfirst.insert(*middle.begin());\n\tmiddle.erase(middle.begin());\n}\n\nwhile(last.size() < k)\n{\n\tlast.insert(*prev(middle.end()));\n\tmiddle.erase(prev(middle.end()));\n}  \n```\n*Since multisets are sorted in nature, the last element in first multiset should be less than or equal to the first element of the middle multiset. \nSimilarly the last element of the middle multiset should be less than or equal to the first element of the last multiset.*\n\nIf the above property is not satisfied, we make adjustments to the multisets. \n```\n        while(*last.begin() < *prev(middle.end()))\n        {\n            middle.insert(*last.begin());\n            last.erase(last.begin());\n            \n            last.insert(*prev(middle.end()));\n            middle.erase(prev(middle.end()));\n        } \n\n        while(*prev(first.end()) > *middle.begin())\n        {\n            middle.insert(*prev(first.end()));\n            first.erase(prev(first.end()));\n            \n            first.insert(*middle.begin());\n            middle.erase(middle.begin());\n        }\n```\n\nHow to calculate the MK Average ?\nWe can add all the element in the middle multiset, and return the average. This approach will have linear complexity. \n\n*We can calculate MK Average in constant time by keeping a running sum of elements in the middle multiset.*\n\ni.e. whenever an element is removed  from the middle multiset, we subtract the element from the sum. Similarly when an element is added to the middle multiset, we add the element to the sum. When ```calculateMKAverage``` function is called we simply return \n```\nreturn q.size() < m ? -1 : sum/middle.size(); // sum is the running sum of elements in middle multiset.\n```\n\nFull code:\n```\nclass MKAverage {\n    \n    private:\n    void adjustHeaps(multiset<int>& first, multiset<int>& middle, multiset<int>& last)\n    {\n        while(first.size() < k)\n        {\n            first.insert(*middle.begin());\n            sum -= *middle.begin();\n            middle.erase(middle.begin());\n        }\n        \n        while(last.size() < k)\n        {\n            last.insert(*prev(middle.end()));\n            sum -= *prev(middle.end());\n            middle.erase(prev(middle.end()));\n        }  \n        \n        while(*last.begin() < *prev(middle.end()))\n        {\n            middle.insert(*last.begin());\n            sum += *last.begin();\n            last.erase(last.begin());\n            \n            last.insert(*prev(middle.end()));\n            sum -= *prev(middle.end());\n            middle.erase(prev(middle.end()));\n        } \n\n        while(*prev(first.end()) > *middle.begin())\n        {\n            sum += *prev(first.end());\n            middle.insert(*prev(first.end()));\n            first.erase(prev(first.end()));\n            \n            first.insert(*middle.begin());\n            sum -= *middle.begin();\n            middle.erase(middle.begin());\n        }\n    }\npublic:\n    int m,k;\n    long long sum = 0;\n    multiset<int> first, last, middle;\n    queue<int> q;\n    \n    MKAverage(int m, int k) {\n        this->m = m;\n        this->k = k;\n    }\n    \n    void addElement(int num) {\n        if(q.size() < m-1)\n        {\n            middle.insert(num);\n            q.push(num);\n        }\n        else if(q.size() == m-1)\n        {\n            auto f = middle.begin();\n            auto l = middle.rbegin();\n            q.push(num);\n            middle.insert(num);\n            int count = 0;\n            while(count < k)\n            {\n                first.insert(*middle.begin());\n                middle.erase(middle.begin());\n                \n                last.insert(*middle.rbegin());\n                middle.erase(prev(middle.end()));\n                \n                count++;\n            }\n            for(auto i : middle) sum += i;\n        }\n        else\n        {\n            q.push(num);\n            auto elem = q.front();\n            q.pop();\n            middle.insert(num);\n            sum += num;\n            \n            if(first.find(elem)!= first.end()){\n                first.erase(first.find(elem));               \n                adjustHeaps(first, middle, last);\n            }\n            \n            else if(middle.find(elem) != middle.end())\n            {\n                sum -= elem;\n                middle.erase(middle.find(elem));\n                adjustHeaps(first, middle, last);\n            }\n            \n            else if(last.find(elem)!= last.end())\n            {\n                last.erase(last.find(elem));                \n                adjustHeaps(first, middle, last);\n            }\n        }\n    }\n    \n    int calculateMKAverage() {\n        return q.size() < m ? -1 : sum/middle.size();\n    }\n};\n```
[]