C++ 100% faster| Priority Queue | Easy Step By Step Explanation
Intuition\n   - The key challenge in maximizing the total happiness of selected children lies in strategically choosing children to minimize the overall "happin
# Intuition\n   - The key challenge in maximizing the total happiness of selected children lies in strategically choosing children to minimize the overall "happiness loss" caused by their selection. Since happiness values decrease after each pick, selecting children with the highest initial happiness first minimizes this loss.\n\n# Approach\n   - We\'ll leverage a priority queue (PQ) to efficiently select children with the highest happiness values.\n\n   - **Prioritize Happiness:** Iterate through the happiness array and insert each happiness value into the priority queue (PQ). The PQ acts as a max-heap, ensuring that the children with the highest happiness are at the top.\n\n   - **Select and Accumulate Happiness:**\n       - Initialize a variable sum to store the total happiness of selected children.\n       - Use a loop to iterate k times (number of selections):\n            - Extract the maximum happiness value (top) from the PQ.\n            - Since happiness decreases by cnt (number of selections made so far) for remaining children, subtract cnt from top to get the actual happiness gained by selecting this child.\n            - If top is still positive (happiness gain exists), add it to the sum.\n            - Decrement cnt to account for the happiness decrease on the next selection.\n            - Remove (pop) the selected child from the PQ.\n\n# Complexity\n- Time complexity:  **O(n * log n)**\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n\n- Space complexity: **O(n)**\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n \n\n# Code\n```\nclass Solution {\npublic:\n  long long maximumHappinessSum(vector<int>& happiness, int k) {\n    priority_queue<int> pq; \n\n    for (int h : happiness) {\n      pq.push(h);\n    }\n\n    long long sum = 0;\n    int cnt = 0;\n    while (k--) {\n      int top = pq.top()-cnt;\n        pq.pop();\n        if(top>0){\n            sum+=top;\n        }\n        cnt++;\n    }\n\n    return sum;\n  }\n};\n\n```\n![Please Upvote4.png](https://assets.leetcode.com/users/images/76505a2b-3063-4094-b08f-08b4cdc128bf_1710042898.3085015.png)\n![Please Upvote3jpeg.png](https://assets.leetcode.com/users/images/76a05d95-99e7-49f4-9aea-3bf635f1b5ed_1710042902.7676334.png)\n
['Array', 'Heap (Priority Queue)', 'C++']