[Python / Go / C++] heap vs BST on sorted array O(NlogN+KlogK)
Python w/ ascending min heap\n\npython\ndef kSum(self, nums, k):\n    res, nums = -sum(max(num, 0) for num in nums), sorted(map(abs, nums))\n    q = [(res + num
*Python* w/ ascending min heap\n\n```python\ndef kSum(self, nums, k):\n    res, nums = -sum(max(num, 0) for num in nums), sorted(map(abs, nums))\n    q = [(res + nums[0], 0)]\n    for _ in range(k - 1):\n        res, i = heapq.heappop(q)\n        if (j := i + 1) < len(nums):\n            heapq.heappush(q, (res + nums[j], j))\n            heapq.heappush(q, (res + nums[j] - nums[i], j))\n    return -res\n```\n\n*Go* w/ descending max heap in 169ms\n\n```go\ntype Node struct {\n\tsum int64\n\ti   int\n}\n\ntype queue []*Node\n\nfunc (q queue) Len() int            { return len(q) }\nfunc (q queue) Less(i, j int) bool  { return q[i].sum > q[j].sum }\nfunc (q queue) Swap(i, j int)       { q[i], q[j] = q[j], q[i] }\nfunc (q *queue) Push(x interface{}) { *q = append(*q, x.(*Node)) }\nfunc (q *queue) Pop() interface{} {\n\ti := len(*q) - 1\n\tx := (*q)[i]\n\t*q = (*q)[:i]\n\treturn x\n}\n\nfunc kSum(nums []int, k int) int64 {\n\tvar (\n\t\tres int64\n\t\tq   queue\n\t)\n\tfor i, num := range nums {\n\t\tif num > 0 {\n\t\t\tres += int64(num)\n\t\t} else {\n\t\t\tnums[i] = -num\n\t\t}\n\t}\n\tsort.Ints(nums)\n\theap.Push(&q, &Node{res - int64(nums[0]), 0})\n\tfor ; k > 1; k-- {\n\t\tx := heap.Pop(&q).(*Node)\n\t\tif j := x.i + 1; j < len(nums) {\n\t\t\theap.Push(&q, &Node{x.sum - int64(nums[j]), j})\n\t\t\theap.Push(&q, &Node{x.sum - int64(nums[j]) + int64(nums[x.i]), j})\n\t\t}\n\t\tres = x.sum\n\t}\n\treturn res\n}\n```\n\n*C++* w/ ascending max priority queue\n\n```c++\nlong long kSum(vector<int> &nums, int k) {\n    long long res = 0;\n    priority_queue<pair<long long, int>> q;\n    for (int i = 0; i < nums.size(); ++i) {\n        if (nums[i] > 0) res += nums[i];\n        else nums[i] = -nums[i];\n    }\n    sort(begin(nums), end(nums));\n    q.push({res - nums[0], 0});\n    while (--k) {\n        auto[sum, i] = q.top(); q.pop();\n        if (int j = i + 1; j < nums.size()) {\n            q.push({sum - nums[j], j});\n            q.push({sum - nums[j] + nums[i], j});\n        }\n        res = sum;\n    }\n    return res;\n}\n```\n\n*C++* w/ ascending min multimap\n\n```c++\nlong long kSum(vector<int> &nums, int k) {\n    long long res = 0;\n    for (int i = 0; i < nums.size(); ++i) {\n        if (nums[i] > 0) res -= nums[i];\n        else nums[i] = -nums[i];\n    }\n    sort(begin(nums), end(nums));\n    multimap<long long, int> m({{res + nums[0], 0}});\n    for (auto it = begin(m); --k; ++it) {\n        auto[sum, i] = *it;\n        if (int j = i + 1; j < nums.size()) {\n            m.insert({sum + nums[j], j});\n            m.insert({sum + nums[j] - nums[i], j});\n        }\n        res = sum;\n    }\n    return -res;\n}\n```
[]