The k-th largest element of the array

Title Link

There are two ways to use the heap:

1. Use the small root heap with the size of the total number of elements. After k elements are popped, the top element of the heap is the k-largest element among all elements.
2. Maintain a K-size large root heap, so that the first k largest elements of all elements are in the heap, and the elements in the heap pop up in turn until the last is the k-largest element.

The following is the code implementation of method 1

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int,vector<int>,less<int> > heap;
        for(auto n:nums) heap.push(n);
        int res=heap.top();
        for(int i=0;i<k-1;i++){
            heap.pop();
            res=heap.top();
        }
        return res;
    }
};

Minimum k number

Title Link

Maintain a k-size large root heap and insert all elements. When the number of elements in the heap exceeds k, the top elements of the heap will be ejected, so that all elements in the last heap will be the minimum number of k (because the large number will be ejected from the heap first)

class Solution {
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        vector<int> vec(k, 0);
        if (k == 0) { // Exclude 0
            return vec;
        }
        priority_queue<int> Q;
        for (int i = 0; i < k; ++i) {
            Q.push(arr[i]);
        }
        for (int i = k; i < (int)arr.size(); ++i) {
            if (Q.top() > arr[i]) {
                Q.pop();
                Q.push(arr[i]);
            }
        }
        for (int i = 0; i < k; ++i) {
            vec[i] = Q.top();
            Q.pop();
        }
        return vec;
    }
};

First k high frequency words

Title Link

To find the problem of element frequency, hash is generally used to count the frequency of elements
Then maintain a small root heap of k size and insert all elements in the hash (the hash can be automatically de duplicated)
The last element in the heap is the first k high-frequency word
As a class, pair is more recommended to use empty_ Back, some performance improvements

Note: the priority queue custom comparison function in C + + is just opposite to the custom comparison functions such as sort. For example, the < less than sign is required to implement the large root heap (it is understood that the array is incremented to the small root heap, but it is not)

class Solution {
public:
    vector<string> topKFrequent(vector<string>& words, int k) {
        unordered_map<string, int> cnt;
        for (auto& word : words) {
            cnt[word]++;
        }
        auto cmp = [](const pair<string, int>& a, const pair<string, int>& b) {
            return a.second == b.second ? a.first < b.first : a.second > b.second;
        };
        priority_queue<pair<string, int>, vector<pair<string, int>>, decltype(cmp)> que(cmp);
        for (auto& it : cnt) {
            que.emplace(it);
            if (que.size() > k) {
                que.pop();
            }
        }
        vector<string> ret(k);
        for (int i = k - 1; i >= 0; i--) {
            ret[i] = que.top().first;
            que.pop();
        }
        return ret;
    }
};

Median of data flow

Title Link

Two heaps are maintained. The large root heap is used to store the smaller part of the elements, and the small root heap is used to store the larger part of the elements
Moreover, in order to ensure that when the total number of elements is odd, the median is always in the large root heap. Therefore, we need to define that once the number of elements in the small root heap exceeds the number of elements in the large root heap, we need to adjust it immediately and add the top elements of the small root heap to the large root heap. At the same time, in order to maintain balance, the number of large root heap elements should be at most one more than the number of small root heap elements.

class MedianFinder {
public:
    /** initialize your data structure here. */
    MedianFinder() {

    }
    priority_queue<int, vector<int>, greater<int>> up; //Small top pile
    priority_queue<int> down; //Large top pile
    void addNum(int num) {
        if (down.empty() || num <= down.top()) down.push(num); //The inserted element is smaller than the top of the big top heap and is inserted into the big top heap.
        else up.push(num); //Otherwise, insert it into the small top pile.
        //Adjust the large top heap and small top heap elements
        if (down.size() == up.size() + 2) {//Adjust when the number of large top heap elements is greater than that of small top heap elements.
            up.push(down.top());
            down.pop();
        } else if (up.size() == down.size() + 1) {//When the number of elements in the small top heap is greater than one element in the small top heap, it shall be adjusted to keep the midpoint on the large top heap.
        //Always keep the number of elements in the left large top heap equal to or greater than the number of elements in the right small top heap
            down.push(up.top());
            up.pop();
        }
    }
    double findMedian() {
        if ((down.size() + up.size()) % 2) return down.top(); //When the total number of elements is odd.
        return (down.top() + up.top()) / 2.0; //When the total number of elements is even.
    }
};

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder* obj = new MedianFinder();
 * obj->addNum(num);
 * double param_2 = obj->findMedian();
 */