Maximum Star Sum of Graph - Simplified (Java)
Maximum Star Sum of the Graph\n\nQuestion Description\n\nGiven an undirected graph with n nodes numbered from 0 to n - 1 and an integer array vals of length n w
### Maximum Star Sum of the Graph\n\n**Question Description**\n\nGiven an undirected graph with `n` nodes numbered from `0` to `n - 1` and an integer array `vals` of length `n` where `vals[i]` denotes the value of the `i`-th node, along with a 2D integer array `edges` where `edges[i] = [ai, bi]` represents an undirected edge between nodes `ai` and `bi`, the task is to find the maximum star sum of the graph.\n\nA star graph is a subgraph with a center node and zero or more neighbors. The goal is to find the maximum sum of the values of the center node and its neighbors, considering at most `k` neighbors.\n\n### Intuition\n\nTo solve this problem, we can use a max-heap to keep track of the maximum values of the neighbors for each node. The approach involves:\n\n1. **Building the Adjacency List**: For each node, maintain a max-heap to store the values of its neighbors.\n2. **Calculating the Maximum Star Sum**: For each node, calculate the sum of the node\'s value and the maximum values of up to `k` neighbors using the max-heap.\n\n### Code and Explanation\n\n#### Class and Main Function\n\n```java\nimport java.util.*;\n\nclass Solution {\n    // Weighted Adjacency List created...\n    Map<Integer, PriorityQueue<Integer>> adjHeap = new HashMap<>();\n    \n    public int maxStarSum(int[] vals, int[][] edges, int k) {\n        for(int i = 0; i < vals.length; i++)    // Mapping maxHeap to each node...\n            adjHeap.put(i, new PriorityQueue<>(Collections.reverseOrder()));\n        \n        for(int[] edge : edges) {\n            // Updating values to the maxHeap...\n            adjHeap.get(edge[0]).offer(vals[edge[1]]);\n            adjHeap.get(edge[1]).offer(vals[edge[0]]);\n        }\n        \n        return maxSum(k, vals);     // Finding the maxSum graph...\n    }\n}\n```\n\n**Explanation:**\n\n- **maxStarSum Function**:\n  - Initializes the adjacency list with max-heaps for each node.\n  - Fills the heaps with the values of neighboring nodes.\n  - Calls the `maxSum` function to calculate the maximum star sum.\n\n#### Max Sum Calculation Function\n\n```java\npublic int maxSum(int k, int vals[]) {\n    int maxSum = Integer.MIN_VALUE;     // variable to store max Star Sum...\n    for(int node : adjHeap.keySet()) {\n        int temp = k;\n        int sum = 0;    // Max k Sum for current node...\n        while(!adjHeap.get(node).isEmpty()) {\n            // If k edges are taken...\n            if(temp == 0)   break;\n            // If adding next edge will decrease the sum...\n            if(sum > sum + adjHeap.get(node).peek())    break;\n            sum += adjHeap.get(node).poll();    // Add the sum to the Star sum...\n            temp--;     // Decrease the remaining edge count...\n        }\n        maxSum = Math.max(sum+vals[node], maxSum);  // Find the max Star Sum...\n    }\n    return maxSum;      // return the max Star Sum...\n}\n```\n\n**Explanation:**\n\n- **maxSum Function**:\n  - Iterates over each node, calculating the sum of the node\'s value and the top `k` values from its heap.\n  - Tracks the maximum star sum encountered during the iteration.\n\n### Complexity\n\n- **Time Complexity**: \\(O(n + m \\log m)\\)\n  - \\(O(n)\\) for initializing the adjacency list.\n  - \\(O(m \\log m)\\) for inserting values into the heaps, where `m` is the number of edges.\n  - \\(O(n \\log k)\\) for calculating the sum for each node, considering up to `k` neighbors.\n\n- **Space Complexity**: \\(O(n + m)\\)\n  - Space required for the adjacency list and heaps.
['Array', 'Greedy', 'Graph', 'Sorting', 'Heap (Priority Queue)', 'Java']