C++ | Build a maxHeap storing the subset sums as a tree (with clear explanations)
After the contest I came here looking for some insights. This is the same method as suggested by other top posts. I had difficulty understanding how the min hea
After the contest I came here looking for some insights. This is the same method as suggested by other top posts. I had difficulty understanding how the min heap method was constructed after reading other posts, in particular why there were two pushes for each node; so I added some explanations here. Two references: [1](https://leetcode.com/problems/find-the-k-sum-of-an-array/discuss/2457783/c%2B%2B-priority-queue-with-explanation-on-the-required-knowledge), [2](https://stackoverflow.com/questions/33219712/find-k-th-minimum-sum-of-every-possible-subset/33220735#33220735).\n\nThe intuition behind the solution is a systematic method to search through all of the `2^n` possible subsequences i.e. all subsets in a binary tree structure. Take the example of `[2, 4, -2]`, we can do it in the following way: we pick the first element as the first node, then we add two child nodes by the following two choices:\n1. replace it by the 2nd node;\n2. add the 2nd node;\n\nWith the above procedure, we get the following binary tree for all the subsets:\n```\n// tree 1\n2_____\n|      \\\n4 __    2,4________\n|    \\     |       \\\n-2  4,-2   2,-2   2,4,-2\n```\nFor the `i`-th node, its left child is always to replace the `i`-th element by the `i+1`-th element, and its right child is always to just add the `i+1`-th element. In this way the binary tree would contain all `2^n-1` possible subsets as its nodes, with one more subset being the empty set. As a reference, below is the same tree as above, but storing the corresponding subset\' element indices instead of the elements themselves:\n```\n// tree 2\n0_____\n|      \\\n1 __    0,1________\n|    \\     |       \\\n2  1,2    0,2      0,1,2\n```\n\nThe above trees are keyed by the index of the corresponding elements in the original array; this is not useful for the problem. Another problem is that the complexity of building the full tree is still exponential, and we need at most log-linear complexity to solve the problem. So one way is to make sure that the nodes with the larger sum values should be added first, in this way we only need to add `k` nodes into the tree and the tree would in fact beome a `maxHeap`. Since a heap insert costs `O(log k)` where `k` is the number of nodes, the time complexity will be `O(k log k)`.\n\nHere we repeat the previous procedure to buid the binary tree but this time keyed by subset sums and in descending order:\n1) the largest sum value `maxSum` will be equal to the sum of all non-negative elements in the original array; this value can be pre-computed;\n2) the 2nd largest sum value will be `max(maxSum - a, maxSum + x)`, where `a` is the smallest positive value and `x` is the largest negative value (largest in the sense that it has the smallest absolute value) in the original array, respectively; if we first convert the array `nums` to include all absolute values, then the expression can simply be `maxSum - a`; this will be the first node in the tree;\n3) with the previous construction procedure, we now add two child nodes; for the left child node, we replace `a` with the next smallest element in `nums` e.g. `b` (note: `b>a`), so we insert `maxSum - b`; for the right child node, we subtract both `a` and `b` so we insert `maxSum - (a+b)`;\n4) next we need to subtracct the next smallest element, say `c`; a problem arises: we have no idea if `c` is larger or smaller than `a+b`, so we won\'t know which node comes first in the final order; this is why we need to maintain the tree as a max heap so that all the inserted nodes will be ordered properly;\n\nIn the previous example, the `maxSum` is 6=2+4. The original `nums` will need to store all absolute values and sorted in ascending order, so `[2,4,-2]` should become `[2,2,4]`. With the above procedure, the max heap for the previous example, storing subset sums, will be as follows:\n```\n// tree 3\n4_____\n|      \\\n4 __    2_______\n|    \\     |     \\\n2     0    0     -2\n```\nNote that the corresponding tree storing element indices will be exactly the same as tree 2. For instance the first node `4=maxSum-nums[0]=6-2=4`, etc.. Here already we can get the subset sums ordered as `6,4,4,2,2,0,0,-2`. All that remains is to limit the number of nodes inserted to the maxHeap to be the first `k-1` nodes (the first node is implicitly `maxSum` so not inserted into the heap), this can be done by using a simple counter.\n\nBelow is the accepted code in C++:\n```\nclass Solution {\npublic:\n    long long kSum(vector<int>& nums, int k) {\n        \n        int n = nums.size();\n        \n        // compute the maxSum = sum of all positive values in `nums`\n        // if nums[i] is negative convert it to absolute value\n        long long maxSum = 0;\n        for (int i = 0; i < n; ++i) {\n            if (nums[i] >= 0)\n                maxSum += nums[i];\n            else\n                nums[i] = abs(nums[i]);\n        }\n        \n        // sort `nums` by ascending order\n        // takes O(n log n)\n        sort(nums.begin(), nums.end());\n        \n        // the maxHeap or max priority queue implements the binary tree keyed by\n        // the sum value of the subset\n        // each node has two possible children\n        // 1) replaces nums[i] with nums[i+1], so childnode.val = node.val + nums[i] - nums[i+1]\n        // 2) add nums[i+1] to be subtracted too, so childnode.val = node.val - nums[i+1]\n        // obviously the index `i` would also need to be stored in the maxHeap along w/t the sum\n        // values, so the elements in the heap is {sum, index}\n        // only first k nodes are needed, for each node the heapify operation takes log k\n        // so it takes O(k log k) time complexity\n        priority_queue<pair<long long, int>> pq;\n        pq.push({maxSum - nums[0], 0});\n\n        // note that first node is always to subtract zero i.e. the sum is maxSum itself\n        // so only need to insert/pop k-1 nodes\n        int count = 0;\n        long long ans;\n        while (!pq.empty() && count < k-1) {\n            auto u = pq.top();\n            pq.pop();\n            long long sub = u.first;\n            int idx = u.second;\n            count++;\n            ans = sub;\n\t\t\t// make sure no overflow\n            if (idx < n-1) {\n                // 1. replace nums[idx] and subtract nums[idx+1]\n                pq.push({sub + nums[idx] - nums[idx+1], idx+1});\n                // 2. keep nums[idx] and further subtract nums[idx+1]\n                pq.push({sub - nums[idx+1], idx+1});\n            }\n        }\n        \n        // if k==1 then return maxSum directly, no subtraction\n        // else return the (k-1)-th subtracted value which is just ans from the while-loop\n        return k == 1 ? maxSum : ans;\n    }\n};\n```\n\nTime complexity: 1) the heap operations take `O(k log k)` for there are `k` nodes in the heap and each heapify i.e. `push` operation takes log time; 2) the array needs to be sorted, which usually takes `O(n log n)` where `n` is the array size. So the total time complexity is `O(n log n + k log k)`.\nSpace complexity: needs to store the `k` nodes in the heap, so takes up `O(k)` additional space.\n\n\n\n\n\n\n\n\n\n\n
[]