The concept of priority queue (heap) is not complicated, the difficulty lies in creating a heap by hand. After you are familiar with this process, you can use C++ when doing questions priority_queue<T>. unfamiliar can refer to here.

0. Leetcode 2099. Find the subsequence of length K with the largest sum

gives you an integer array nums and an integer k . You need to find the subsequence of length k in nums with the largest sum of .
Please return any subsequence of integers of length k.
A subsequence is defined as an array obtained by removing some elements from an array without changing the order of the remaining elements.

Analysis and Answers

It can be used as sorting, after using heap sort, select the largest k k k. Here's the first pile of writing:

class Solution {
    int numIdx[2000];
    unordered_map<int, int> id2Num;
    int tail; // pos to insert new element
    
public:
    vector<int> maxSubsequence(vector<int>& nums, int k) {
        tail = 0;
        // Construct large top heap
        for (int i = 0; i < nums.size(); ++i) {
            id2Num[i] = nums[i];
            numIdx[tail++] = i;
            // float up
            int curPos(tail - 1);
            int prePos = (curPos - 1) / 2;
            while (prePos >= 0) {
                if (id2Num[numIdx[curPos]] > id2Num[numIdx[prePos]]) {
                    int tmp = numIdx[curPos];
                    numIdx[curPos] = numIdx[prePos];
                    numIdx[prePos] = tmp;
                    curPos = prePos;
                    prePos = (curPos - 1) / 2;
                } else {
                    break;
                }
            }
        }
        
        // Get the first k elements
        vector<int> vec;
        while (k--) {
            vec.push_back(numIdx[0]);
            numIdx[0] = numIdx[tail - 1];
            // sink
            int curPos(0);
            int lIdx = curPos * 2 + 1;
            
            while (lIdx < tail - 1) {
                int sonIdx = lIdx;
                int rIdx = curPos * 2 + 2;
                if (id2Num[numIdx[sonIdx]] < id2Num[numIdx[rIdx]]) {
                    sonIdx = rIdx;
                }
                if (id2Num[numIdx[curPos]] < id2Num[numIdx[sonIdx]]) {
                    int curNum = numIdx[curPos];
                    numIdx[curPos] = numIdx[sonIdx];
                    numIdx[sonIdx] = curNum;
                    curPos = sonIdx;
                    lIdx = curPos * 2 + 1;
                } else {
                    break;
                }
            }
            tail--;
        }
        sort(vec.begin(), vec.end());
        vector<int> result;
        for (int i = 0; i < vec.size(); ++i) {
            result.push_back(nums[vec[i]]);
        }
        
        return result;
    }
};

We can also build a small top heap, which will be the front k k After k elements are placed in the heap, search the remaining elements in the array. If the current element is larger than the top element of the heap, delete the top element of the heap and insert the current element:

class Solution {
    struct Data {
        int idx;
        int num;

        bool operator<(const Data& o) const {
            if (num == o.num) {
                return idx < o.idx;
            }
            return num > o.num;
        }
    };
    priority_queue<Data> q;

public:
    vector<int> maxSubsequence(vector<int>& nums, int k) {
        for (int i = 0; i < k; ++i) {
            // Build a heap of size k
            Data curData;
            curData.idx = i;
            curData.num = nums[i];
            q.push(curData);
        }

        for (int i = k; i < nums.size(); ++i) {
            // Make sure the heap is the k largest element in [0, i]
            Data curData = q.top();
            if (curData.num < nums[i]) {
                // Pop the smallest element in the heap and put the current element
                q.pop();
                Data cData;
                cData.idx = i;
                cData.num = nums[i];
                q.push(cData);
            }
        }

        // Get subscript and sort
        vector<int> resultIdx;
        while (!q.empty()) {
            Data cur = q.top();
            resultIdx.push_back(cur.idx);
            q.pop();
        }
        
        // Select the corresponding element according to the subscript
        sort(resultIdx.begin(), resultIdx.end());
        vector<int> result;
        for (int i = 0; i < resultIdx.size(); ++i) {
            result.push_back(nums[resultIdx[i]]);
        }

        return result;
    }
};

1. Leetcode 1792. Maximum Average Pass Rate

A school has some classes, each class has some students, and now each class has a final exam. Given a two-dimensional array classes , where classes[i] = [passi, totali] , it means that you know in advance that there are totali students in the i-th class, and only passi students can pass the exam.
Give you an integer extraStudents , which means extraStudents extra smart students who are guaranteed to pass the final exam in any class. You need to assign each of these extraStudents a class to maximize the average pass rate for all classes.
The pass rate for a class is equal to the number of students who passed the exam in that class divided by the total number of students in the class. The average pass rate is the sum of the pass rates for all classes divided by the number of classes.
Please return the maximum average pass rate after placing these extraStudents in the corresponding class. Results within 10-5 of the standard answer are considered correct.

Analysis and Answers

The key to this question is to clarify what the object compared in the priority queue is. Since there can be k k There are k students who must pass, so each time one student is assigned to the class where the passing rate changes the most after one person is added, that is:
m a x i x i + 1 y i + 1 − x i y i max_i \frac{x_i + 1}{y_i + 1} - \frac{x_i}{y_i} maxi​yi​+1xi​+1​−yi​xi​​

class Solution {
    struct Pair {
        int a;
        int b;

        Pair(int _a, int _b) {
            a = _a;
            b = _b;
        }

        void update() {
            a++;
            b++;
        }
        
        double getDelta() const {
            return (double)(a + 1) / (b + 1) - (double)a / b;
        }

		// Note the delta value of the element being compared when inserting
        bool operator < (const Pair& o) const {
            return getDelta() < o.getDelta();
        }
    };

public:
    double maxAverageRatio(vector<vector<int>>& classes, int extraStudents) {
        priority_queue<Pair> q;
        int n = classes.size();
        for (int i = 0; i < n; ++i) {
            q.push(Pair(classes[i][0], classes[i][1]));
        }

        while (extraStudents--) {
            // Each time to find the largest change in the pass rate, insert
            Pair curPair = q.top();
            q.pop();
            curPair.update();
            q.push(curPair);
        }

        double result(0);
        int num = q.size();
        while (!q.empty()) {
            result += (double)q.top().a / q.top().b;
            q.pop();
        }

        return result / num;
    }
};

2. Leetcode 1499. Maximum Satisfying Inequality

gives you an array points and an integer k . Each element in the array represents the coordinates of a point on a two-dimensional plane, and is sorted according to the value of the abscissa x from small to large. That is, points[i] = [xi, yi], and at 1 < = I < J < = points Under the premise of length, Xi < XJ is always true
Please find the maximum value of yi + yj + |xi - xj|, where |xi - xj| < = K and 1 < = I < J < = points length.
The test data of the topic ensures that there is at least one pair of points that can satisfy | Xi - XJ | < = K

Analysis and Answers

There needs to be some conversion here, because x i < x j x_i < x_j xi <xj, so the original formula y i + y j + ∣ x i − x j ∣ = y i + y j + x j − x i y_i + y_j + |x_i - x_j| = y_i + y_j + x_j - x_i yi​+yj​+∣xi​−xj​∣=yi​+yj​+xj​−xi​, since for each j j For j, x j + y j x_j + y_j xj​+yj​ is a fixed value, so the problem is transformed into finding y i − x i y_i - x_i yi​−xi​ maximum value, and x j − x i ≤ k x_j - x_i \leq k xj​−xi​≤k, it is easy to think of using a heap to solve:

class Solution {
    struct Data {
        int idx;
        int val;

        bool operator < (const Data& o) const {
            if (val == o.val) {
                return idx > o.idx;
            }
            return val < o.val;
        }
    };

    priority_queue<Data> q; // big top heap

public:
    int findMaxValueOfEquation(vector<vector<int>>& points, int k) {
        int result(INT_MIN);
        // y_i + y_j + x_j - x_i (x_i < x_j)
        // So for each j, just find the largest y_i - x_i        
        int n = points.size();
        for (int i = 0; i < n; ++i) {
            int xi = points[i][0];
            int yi = points[i][1];
            int del = yi - xi;
            
            // Find the maximum result at index i
            while (!q.empty()) {
                Data topData = q.top();
                if (xi - topData.idx > 0 && xi - topData.idx <= k) {
                	// Find the maximum result when the index is i, break
                    if (topData.val + xi + yi > result) {
                        result = topData.val + xi + yi;
                    }
                    break;
                } else {
                	// If the top element of the heap and i exceed k, then delete
                    while (xi - topData.idx > k && !q.empty()) {
                        q.pop();
                        topData = q.top();
                    }
                }
            }

            Data tmp;
            tmp.idx = xi;
            tmp.val = del;
            q.push(tmp); // Insert the current element into the heap
        }

        return result;
    }
};

3. Leetcode 2163. Minimum difference of sum after removing elements

You are given a 0-based integer array nums with 3 * n elements.
You can remove exactly n elements from nums, and the remaining 2 * n elements will be split into two equal-sized parts.
The first n elements belong to the first part, and their sum is denoted sumfirst .
The next n elements belong to the second part, and their sum is denoted sumsecond .
The difference between the sums of the two parts is denoted sumfirst - sumsecond .
Let's say sumfirst = 3 and sumsecond = 2 , their difference is 1 .
For another example, sumfirst = 2 and sumsecond = 3 , the difference between them is -1 .
Please return the minimum value of the difference between the remaining two parts after removing n elements.

Analysis and Answers

This question first wrote a time-out answer, and then wrote the correct answer with reference to the solution...
Let’s talk about ideas first, because before n n n elements must be in s u m f i r s t sum_{first} sumfirst​ in, after n n n elements must be in s u m s e c o n d sum_{second} sumsecond​ , so the question focuses on the middle n n A division of n elements. For this you can traverse the middle n n n elements, with each element as a cut point, the [ 0 , n + i ] [0, n + i] [0,n+i] is divided into the first half set, [ n + i + 1 , 3 n ] [n + i + 1, 3n] [n+i+1,3n] is divided into the second half of the set, and then find the first half of the set n n n smallest elements; in the second half of the set n n The n largest elements can get the minimum value of the difference required in the question.
Here, if you directly traverse and construct two priority queues, it will time out, so before using n n n elements construct the first half set, after using n n n elements to construct the second half set, and then from [ n , 2 n ] [n, 2n] [n,2n] Traverse, update the first half of the collection with the current element, keep n n n smallest elements; from [ 2 n , 3 n ] [2n, 3n] [2n,3n] traverse in reverse order, update the second half of the collection with the current element, keep n n n largest elements:

class Solution {
    int n2Del;
    priority_queue<int, vector<int>, less<int>> q0; // big top heap
    priority_queue<int, vector<int>, greater<int>> q1; // small top pile

public:
    long long minimumDifference(vector<int>& nums) {
        // Divide into two heaps, find the largest and smallest respectively; loop over the n in the middle
        int n = nums.size();
        n2Del = n / 3;
        long long result(LONG_MAX);
        // the first n elements, removing the largest each time
        // [0, n]; [0, n - 1]; ... [0, 2n]
        vector<long long> numFirstVec;
        long long numFirst(0);
        for (int i = 0; i < n2Del; ++i) {
            q0.push(nums[i]);
            numFirst += nums[i];
        }
        numFirstVec.push_back(numFirst);
        for (int i = n2Del; i < 2 * n2Del; ++i) {
        	// Loop through the largest element
            int cur = q0.top();
            if (cur > nums[i]) {
                q0.pop();
                q0.push(nums[i]);
                numFirst -= cur;
                numFirst += nums[i];
            }
            numFirstVec.push_back(numFirst);
        }

        // the last n elements, each time removing the smallest
        // [2n, 3n]; [2n - 1, 3n]; ... [n, 3n]
        vector<long long> numSecondVec;
        long long numSecond(0);
        for (int i = 2 * n2Del; i < n; ++i) {
            q1.push(nums[i]);
            numSecond += nums[i];
        }
        numSecondVec.push_back(numSecond);
        for (int i = 2 * n2Del - 1; i >= n2Del; --i) {
          	// Loop through the smallest element
            int cur = q1.top();
            if (cur < nums[i]) {
                q1.pop();
                q1.push(nums[i]);
                numSecond -= cur;
                numSecond += nums[i];
            }
            numSecondVec.push_back(numSecond);
        }

		// Note that there is a one-to-one correspondence after the reverse order, and the minimum value is calculated.
        reverse(numSecondVec.begin(), numSecondVec.end());
        for (int i = 0; i < numFirstVec.size(); ++i) {
            if (result > numFirstVec[i] - numSecondVec[i]) {
                result = numFirstVec[i] - numSecondVec[i];
            }
        }
        
        return result;
    }
};

Summarize

The concept of priority queues is well understood, but in practical applications, how to accurately find the indicators used by sorting is very important.