Priority Queue Solution | Full Explanation
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem requires finding the maximum possible sum of happiness after performing k o
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem requires finding the maximum possible sum of happiness after performing k operations. Each operation involves selecting the topmost happiness value from the given vector and subtracting a decreasing value from it. \n\nTo maximize the sum of happiness, we want to select the highest happiness values possible and minimize the amount subtracted from them.\n\nThis can be done using priority queue to find maximum happiness, and a variable `curr_sub` which tracks the subtraction that needs to be done from remaining elements. \n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n- Initialize variables `curr_sub` to keep track of the current subtraction that is needed and `max_happ`` to store the maximum happiness.\n- Create a priority queue to store the elements.\n- Insert all elements into the priority queue.\n- Iterate while there are remaining operations to perform (k > 0), and there are still elements in the priority queue, and the top element subtracted by `curr_sub` is still valid.\n- Inside the loop:\n    - Calculate the current sum by applying the current modifier to the top element of the priority queue.\n    - Add this current sum to the total sum.\n    - Remove the top element from the priority queue.\n    - Decrement curr_sub as now 1 needs to be subtracted from happiness of all children.\n    - Decrease the remaining operations (k) by 1.\n- Return the maximum sum obtained.\n\n# Complexity\n- Time complexity: O(NlogN)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:O(n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    long long maximumHappinessSum(vector<int>& happiness, int k) {\n        long long int curr_sub = 0, max_happ = 0;\n        \n        priority_queue<int>pq;\n        for(int h:happiness){\n            pq.push(h);\n        }\n        \n        while(k>0 and pq.size()>0 and pq.top() + curr_sub >= 0) {\n            int curr_happ = pq.top() + curr_sub;\n            max_happ += curr_happ;\n            pq.pop();\n            curr_sub -= 1;\n            k--;\n        }\n        return max_happ;\n    }\n};\n```
['C++']