min-Heap [ Intuition ]
Intuition 1:\n > A star graph is a subgraph of the given graph having a center node containing 0 or more neighbors.\n   \n  This line of question gives a intuit
# Intuition 1:\n > A star graph is a subgraph of the given graph having a center node containing 0 or more neighbors.\n   \n  This line of question gives a intuition that any `node` can be a `star node`.\n    \n# Intuition 2:\n>  star graph containing at most k edges.\n    \nThis line states that we have to take atmost `k top value nodes` which are `positive` and directly connected to a node which is giving us hint of using a `heap`.\n# Why we discard negative?? \nBecause it will decrease the star sum of node which we don\'t want.\n    \n **Combining Above Intuitions, we deduce following steps :**\n    \n   + We will make a graph where every node will have a `min-heap` to filter `<= top k largest` positive directly connected nodes.\n   + We will also maintain a array where we will store sum of  top k positive neighbours corresponding to every node with the help of priority_queue \n   + By following the above two steps, we will have star sum for every node & we will simply return maximum value among all star sum of nodes.\n\n# C++\n     int maxStarSum(vector<int>& vals, vector<vector<int>>& edges, int k) {\n        vector<int> sum = vals;\n        vector<priority_queue<int, vector<int> , greater<int>>> G(vals.size());\n        for(auto e : edges){\n            int u = e[0], v = e[1];\n            \n            if(vals[v] > 0){\n                G[u].push(vals[v]);\n                sum[u] += vals[v];\n\t\t\t\t// Remove nodes and reduce sum if heap has > k nodes\n                if(G[u].size() > k){\n                    sum[u] -= G[u].top();\n                    G[u].pop();\n                }\n            }\n            \n            if(vals[u] > 0){\n                G[v].push(vals[u]);\n                sum[v] += vals[u];\n\t\t\t\t// Remove nodes and reduce sum if heap has > k nodes\n                if(G[v].size() > k){\n                    sum[v] -= G[v].top();\n                    G[v].pop();\n                }\n            }   \n        }\n        return *max_element(begin(sum), end(sum));\n    }\n> Time - O(nlogn)\n\n> Space - O(n)
['C']