Algorithms & Data Structures : Heap / Priority Queue / Binary Heap Problems

Problem

LeetCode 215. Kth Largest Element in an Array
[Priority Queue]

LeetCode : 2410. Maximum Matching of Players With Trainers
[Priority Queue]

LeetCode : 2233. Maximum Product After K Increments
[Priority Queue][Greedy]

LeetCode : 2144. Minimum Cost of Buying Candies With Discount
[Greedy][Sorting][Priority Queue]

LeetCode : 2335. Minimum Amount of Time to Fill Cups
[Priority Queue][Greedy]

LeetCode 215. Kth Largest Element in an Array

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int> pq;
        for(int i = 0;i < nums.size();i++) {
            pq.push(nums[i]);
        }
        
        for(int i = 0;i < k - 1;i++) {
            pq.pop();
        }
        
        return pq.top();
    }
};

LeetCode : 2410. Maximum Matching of Players With Trainers

class Solution {
public:
    int matchPlayersAndTrainers(vector<int>& players, vector<int>& trainers) {
        priority_queue<int> playpq;
        priority_queue<int> trainpq;
        
        for(int i = 0;i < players.size();i++) {
            playpq.push(players[i]);
        }
        for(int i = 0;i < trainers.size();i++) {
            trainpq.push(trainers[i]);
        }        
        
        int ans = 0;
        while(!playpq.empty() && !trainpq.empty()) {
            if(playpq.top() <= trainpq.top()) {
                playpq.pop();
                trainpq.pop();
                ans++;
            } else {
                playpq.pop();
            }
        }
        
        return ans;
    }
};

LeetCode : 2233. Maximum Product After K Increments

// 一定要增加最小的數
#define LL long long
class Solution {
public:
    int maximumProduct(vector<int>& nums, int k) {
        priority_queue<int, vector<int>, greater<int>> pq;
        for(int i = 0;i < nums.size();i++) {
            pq.push(nums[i]);
        }
        for(int i = 0;i < k;i++) {
            int nown = pq.top();
            pq.pop();
            nown++;
            pq.push(nown);
        }
        
        LL ans = 1;
        while(!pq.empty()) {
            ans = (ans * pq.top()) % 1000000007;
            pq.pop();
        }
        
        return ans;
    }
};

LeetCode : 2144. Minimum Cost of Buying Candies With Discount

class Solution {
public:
    int minimumCost(vector<int>& cost) {
        priority_queue<int> pq;
        for(int i = 0;i < cost.size();i++) {
            pq.push(cost[i]);
        }
        int ans = 0;
        int num = 0;
        while(!pq.empty()) {
            num++;
            if (num % 3 != 0) {
                ans += pq.top();
            }
            pq.pop();
        }
        return ans;
    }
};

LeetCode : 2335. Minimum Amount of Time to Fill Cups

// priority queue
class Solution {
public:
    int fillCups(vector<int>& amount) {
        priority_queue<int> pq;
        int ans = 0;
        for(int i = 0;i < amount.size();i++) {
            if(amount[i] > 0) {
                pq.push(amount[i]);
            }
        }
        while(!pq.empty()) {
            if(pq.size() > 1) {
                int tmp1, tmp2;
                tmp1 = pq.top();
                pq.pop();
                tmp2 = pq.top();
                pq.pop();
                tmp1--;
                tmp2--;
                if(tmp1 > 0) {
                    pq.push(tmp1);
                }
                if(tmp2 > 0) {
                    pq.push(tmp2);
                }
                ans++;
            } else {
                ans += pq.top();
                pq.pop();              
            }
        }
        return ans;
    }
};