4 Heaps, 1 Queue / List | 50.00% speed
This solution is referenced from C++ 3 multisets by Izl124631x\nI don\'t know how to implement ordered set with duplicates in javascript, or lazy update / delet
This solution is referenced from [C++ 3 multisets by Izl124631x](https://leetcode.com/problems/finding-mk-average/discuss/1152418/C%2B%2B-3-multisets)\nI don\'t know how to implement `ordered set` with `duplicates` in `javascript`, or `lazy update / delete` in `Heap`\nSo I will just implement and use `Heap` in a intuitive way, it\'s mostly sufficient, since solution using `multiset` are dealing mostly `min` and `max` of the `Heap`\n\nThe idea is to have 3 balanced `Heap` , and 1 copy `Heap`\n* `Left Heap`, storing smallest `k`s, implemented in `Max Heap`\n* `Mid Heap`, storing numbers which forms actual sum, implemented in `Min Heap`\n* `Mid Copy Heap`, this is redundant `Heap`, which is just to get the `max` of `Mid Min Heap`, this follows every action of `Mid Min Heap` when adding an element. This obviusly needs to improve, since it\'s waste of memory. But you would notice in my solution below, I didn\'t have this, instead I just use `O(m)` to get the `max`. I\'m lazy to copy paste.\n* `Right Heap`, storing largest `k`s, implemented in `Min Heap`\n\nSo this way, the four `Heap`s form a `Moving Window` and could transfer `min` and `max` between each other, please refer to `Leetcode 480 Sliding Window Median` for similar idea\n\nNote: for the `queue`, I\'m lazy to implement the `Queue` with `LinkedList`, instead I just use `array.shift`\n```\nclass MKAverage {\n    constructor(m, k) {\n        this.m = m;\n        this.k = k;\n        this.sum = 0;\n        this.left = new Heap((a, b) => a > b);\n        this.mid = new Heap((a, b) => a < b)\n        this.right = new Heap((a, b) => a < b)\n        this.q = [];\n    }\n    \n    addElement(num) {\n\n        // add new num\n        if (this.q.length < this.m) {\n            this.mid.push(num);\n        }\n        this.q.push(num);\n        if (this.q.length === this.m) {\n            for (let i = 0; i < this.k; ++i) {\n                this.left.push(this.mid.pop());\n            }\n            for (let i = 0; i < this.k; ++i) {\n                this.right.push(this.mid.popMax());\n            }\n            this.sum += this.mid.sum\n        } else if (this.q.length > this.m) {\n            if (num < this.left.top()) {\n                this.left.push(num);\n                const value = this.left.pop();\n                this.mid.push(value);\n                this.sum += value; \n            } else if (num > this.right.top()) {\n                this.right.push(num);\n                const value = this.right.pop();\n                this.mid.push(value);\n                this.sum += value;\n            } else {\n                this.mid.push(num)\n                this.sum += num;\n            }\n            \n            // remove old num\n            const value = this.q.shift();\n            if (this.mid.has(value)) {\n                this.mid.remove(value);\n                this.sum -= value;\n            } else if (this.right.has(value)) {\n                this.right.remove(value)\n            } else {\n                this.left.remove(value)\n            }\n\n            // balance three heaps\n            if (this.left.size < this.k) {\n                const value = this.mid.pop();\n                this.left.push(value);\n                this.sum -= value;\n            } else if (this.right.size < this.k) {\n                const value = this.mid.popMax();\n                this.right.push(value);\n                this.sum -= value;\n            }\n        }\n    }\n    \n    calculateMKAverage() {\n        return this.q.length === this.m ? Math.trunc(this.sum / (this.m - 2 * this.k)) : -1;\n    }\n};\n\nclass Heap {\n    constructor(compare) {\n        this.store = [];\n        this.compare = compare;\n        this.index = {};\n    }\n    \n    top() {\n        return this.store[0];\n    }\n    \n    get size() {\n        return this.store.length;\n    }\n    \n    isEmpty() {\n        return this.size === 0;\n    }\n\n    has(value) {\n        return Boolean(this.index[value] && this.index[value].size)\n    }\n    \n    push(value) {\n        this.store.push(value);\n        const i = this.store.length - 1;\n        if (!this.index[value]) this.index[value] = new Set([i]);\n        else this.index[value].add(i)\n        this.heapifyUp(i);\n    }\n    \n    remove(value) {\n        const i = this.index[value].values().next().value;\n        this.index[value].delete(i);\n        if (i === this.store.length - 1) return this.store.pop();\n        this.store[i] = this.store.pop()\n        this.index[this.store[i]].delete(this.store.length);\n        this.index[this.store[i]].add(i);\n        this.heapifyDown(this.heapifyUp(i));\n    }\n\n    popMax() {\n        const max = Math.max(...this.store);\n        this.remove(max);\n        return max;\n    }\n\n    get sum() {\n        return this.store.reduce((p, c) => p + c, 0);\n    }\n    \n    pop() {\n        const value = this.store[0];\n        this.index[value].delete(0);\n        if (this.store.length < 2) return this.store.pop();\n        this.store[0] = this.store.pop();\n        this.index[this.store[0]].delete(this.store.length);\n        this.index[this.store[0]].add(0);\n        this.heapifyDown(0);\n        return value;\n    }\n    \n    heapifyDown(parent) {\n        const childs = [1,2].map((n) => parent * 2 + n).filter((n) => n < this.store.length);\n        let child = childs[0];\n        if (childs[1] && this.compare(this.store[childs[1]], this.store[child])) {\n            child = childs[1];\n        }\n        if (child && this.compare(this.store[child], this.store[parent])) {\n            const childVal = this.store[child];\n            const parentVal = this.store[parent];\n            this.store[child] = parentVal;\n            this.store[parent] = childVal;\n            this.index[childVal].delete(child);\n            this.index[childVal].add(parent);\n            this.index[parentVal].delete(parent);\n            this.index[parentVal].add(child);\n            return this.heapifyDown(child);\n        }\n        return parent;\n    }\n    \n    heapifyUp(child) {\n        const parent = Math.floor((child - 1) / 2);\n        if (child && this.compare(this.store[child], this.store[parent])) {\n            const childVal = this.store[child];\n            const parentVal = this.store[parent];\n            this.store[child] = parentVal;\n            this.store[parent] = childVal;\n            this.index[childVal].delete(child);\n            this.index[childVal].add(parent);\n            this.index[parentVal].delete(parent);\n            this.index[parentVal].add(child);\n            return this.heapifyUp(parent);\n        }\n        return child;\n    }\n}\n```
['Heap (Priority Queue)', 'JavaScript']