[Python] From Brute Force to Optimal. MinHeap O(V + E log(K)) solution.
1) Brute Force (using sort)\nBuild an adjacency list for each vertex in the graph. In a final pass, sort each adjacency list and compute the maximum possible st
# 1) Brute Force (using sort)\nBuild an adjacency list for each vertex in the graph. In a final pass, sort each adjacency list and compute the maximum possible star sum using at most K neighbors for each vertex.\n\n```Python\nclass Solution:\n    def maxStarSum(self, vals: List[int], edges: List[List[int]], K: int) -> int:\n        # T: O(E + V * K + V log(V)), S: O(V)\n        V, E = len(vals), len(edges)\n        adjList = [[] for _ in range(V)]\n        for u, v in edges: # T: O(E)\n            adjList[u].append(v)\n            adjList[v].append(u)\n            \n        ans = -math.inf\n        for u in range(V): # T: O(V * K)\n            adjList[u].sort(key=lambda node: vals[node], reverse=True) # T: O(V log(V)) in total\n            starSum = vals[u]\n            for i in range(min(K, len(adjList[u]))):\n                if vals[adjList[u][i]] <= 0: continue\n                starSum += vals[adjList[u][i]]\n            ans = max(ans, starSum)\n\n        return ans\n```\n\n# 2) MinHeap (optimal)\nInstead of adding all the neighbors of a node to the adjacency list, we can only add the K maximum ones with the help of a MinHeap.\n- Neighbors with a value <= 0 contribute nothing to the star and must be skipped.\n- We simply add nodes until the adjacency list has exactly K elements.\n- If we see a better candidate, that is, a new neighbor with a value greater than the current minimum at the top of the MinHeap we swap them.\n\nWe also use a hashtable to keep track of the star sum for each vertex so that we don\'t have to do additional O(K) work.\n\n```Python\nclass Solution:\n    def maxStarSum(self, vals: List[int], edges: List[List[int]], K: int) -> int:\n        # T: O(E log(K) + V), S: O(V)\n        V, E = len(vals), len(edges)\n        adjList = [[] for _ in range(V)]\n        maxSum = [0] * V\n        for u, v in edges: # T: O(E)\n            for u, v in [(u, v), (v, u)]: # undirected edges are bidirectional\n                if vals[v] <= 0: continue\n\n                if len(adjList[u]) < K:\n                    heapq.heappush(adjList[u], vals[v])\n                    maxSum[u] += vals[v]\n                elif vals[v] > adjList[u][0]:\n                    maxSum[u] -= adjList[u][0]\n                    maxSum[u] += vals[v]\n                    heapq.heapreplace(adjList[u], vals[v])\n\n        return max(vals[u] + maxSum[u] for u in range(V)) # T: O(V)\n```
['Python3']