[C++] Max Heap (Explained 🙂)
\n\u2022 Find sum of +ve numbers. (Max Sum)\n\u2022 Prepare a sorted array of absolute values of the given array\n\u2022 push(sum - a[0], 0) to a max heap.\n\u2
\n\u2022 Find sum of +ve numbers. (Max Sum)\n\u2022 Prepare a sorted array of absolute values of the given array\n\u2022 push(sum - a[0], 0) to a max heap.\n\u2022 for k-1 iterations do\n    pop the top from heap (say {sum, i})\n    push(sum - a[i+1] + a[i], i+1)\n    push(sum - a[i+1], i+1)\n    \n> Basically we are simulating the knapsack procedure iteratively.\n\n##### Example\n\n```\nQ: a[] = {2, -2, 4}, k = 5\n\nMAX_SUM = 6 {2, 4}\nABS_ARR = {2, 2, 4} \n\n(6-2,0)\n(4,0) | (4,1) (2,1)\n(4,1) | (2,2) (2,1) (0,2)\n(2,2) | (2,1) (0,2)\n(2,1) | (0,2) (0,2) (-2,2)\n\nANS = 2\n```\n</br>\n\n##### C++ Solution\n```\nstruct Solution {\n    \n    int n, i;\n    long long ans = 0;\n    priority_queue<pair<long long, int>> q;\n    \n    long long kSum(vector<int> &a, int k) {\n        \n        n = a.size();\n        \n        for (auto &x : a) {\n            if (x >= 0) ans += x;\n            else x = -x;\n        }\n        \n        sort(a.begin(), a.end());\n        q.emplace(ans - a[0], 0);\n        \n        while (--k) {\n            tie(ans, i) = q.top();\n            q.pop();\n            \n            if (i+1 < n) {\n                q.emplace(ans - a[i+1] + a[i], i+1);\n                q.emplace(ans - a[i+1], i+1);\n            }\n        }\n        \n        return ans;\n    }\n};\n```\nTC: O(N\u2022Log(N) + K\u2022Log(K))\nSC: O(K)
['C', 'Heap (Priority Queue)']