Priority Queue of Size K: Simple!!
Intuition\nBuild edges for each value O(E): Creates a list of neighbors for each index, storing the values of neighboring nodes.\n\nO(E): Iterates over each edg
# Intuition\nBuild edges for each value O(E): Creates a list of neighbors for each index, storing the values of neighboring nodes.\n\nO(E): Iterates over each edge, adding the negative values of neighbors to each node\'s list in neighbors.\n\nHeapify it O(E): Applies heapify to each sublist in neighbors to structure them as min-heaps.\n\nCan try a combo for each vertex O(k * V): For each vertex, attempts to maximize the sum of k largest negative neighbors.\n\n# Complexity\n- Time complexity:\nO(E + k * V)\n\n- Space complexity:\nO(E)\n\n# Code\n```python3 []\nimport heapq\nclass Solution:\n    def maxStarSum(self, vals: List[int], edges: List[List[int]], k: int) -> int:\n        # total time complexity O(E + k * V)\n\n        # space complexity O(E)\n\n        # build edges for each value O(E): [for each index: [value of neighbors]]\n        neighbors = [[] for _ in vals]\n        \n        # O(E)\n        for left, right in edges:\n            neighbors[left].append(-vals[right])\n            neighbors[right].append(-vals[left])\n\n        # heapify it O(E)\n        # O(E)\n        for sublist in neighbors:\n            heapq.heapify(sublist)\n\n        # can try a combo for each vertex O(k * V)\n        max_val = float("-inf")\n\n        for i, sublist in enumerate(neighbors):\n            curr = vals[i] \n            for i in range(k):\n                if sublist:\n                    to_add = heapq.heappop(sublist)\n                    if to_add >= 0:\n                        break\n                    curr -= to_add\n                else:\n                    break\n            \n\n            max_val = max(max_val, curr)\n        \n        return max_val if max_val != float("-inf") else 0\n\n\n    \n        \n```
['Python3']