//https://leetcode.cn/problems/last-stone-weight/
//最后一块石头的重量
class Solution {
public:
    int lastStoneWeight(vector<int>& stones) {
        priority_queue<int> pq;
        for(int i = 0; i < stones.size(); ++i)
            pq.push(stones[i]);

        while(pq.size() > 1)
        {
            int a = 0;
            int b = 0;
            int c = 0;
            if(pq.size())
            {
                a = pq.top();
                pq.pop();
            }

            if(pq.size())
            {
                b = pq.top();
                pq.pop();
            }

            c = abs(a-b);
            if(c != 0)
            {
                pq.push(c);
            }
        }

        if(pq.size() < 1)
            return 0;

        return pq.top();
    }
};

//////////////////////////////////////////////////////////////////////////////////////////////////////

//https://leetcode.cn/problems/kth-largest-element-in-a-stream/
//数据流中的第k大元素
class KthLargest {
public:
    KthLargest(int k, vector<int>& nums) {
        _k = k;
        for(auto e : nums)
        {
            heap.push(e);
            if(heap.size() > _k) heap.pop();
        }
    }
    
    int add(int val) {
        heap.push(val);
        if(heap.size() > _k) heap.pop();

        return heap.top();
    }
private:
    priority_queue<int,vector<int>,greater<int>> heap;
    int _k;
};

//////////////////////////////////////////////////////////////////////////////////////////////////////


//https://leetcode.cn/problems/g5c51o/description/
//前K个高频元素
class Solution {
    struct cmp
    {
        bool operator()(const pair<int,int> a, const pair<int,int> b)
        {
            return a.second > b.second;
        }
    };
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int,int> hash;
        priority_queue<pair<int,int>, vector<pair<int,int>>, cmp> heap;
        vector<int> ret;

        for(int i = 0; i < nums.size(); ++i)
            hash[nums[i]]++;

        for(auto e : hash)
        {
            heap.push(e);
            if(heap.size() > k)
                heap.pop();
        }

        while(heap.size() && k--)
        {
            auto[a,b] = heap.top();
            heap.pop();
            ret.push_back(a);
        }
        return ret;
    }
};

//////////////////////////////////////////////////////////////////////////////////////////////////////

为什么选最大的前k个元素要用小根堆？
排小根堆的话，来了大的元素他就往下沉，小的元素就被浮上来了，当堆中的数据个数超过 k 时，取堆顶元素之后，pop( ) 掉的就是堆中最小的元素。相当于大元素会把此时堆中最小的元素挤出堆。

大根堆反之。

//https://leetcode.cn/problems/top-k-frequent-words/
//前K个高频单词
class Solution {
    struct cmp{
        bool operator()(pair<string,int> a, pair<string,int> b)
        {
            if(a.second == b.second)
                return a.first < b.first;
            return a.second > b.second;
        }
    };
public:
    vector<string> topKFrequent(vector<string>& words, int k) {
        unordered_map<string,int> hash;
        priority_queue<pair<string,int>, vector<pair<string,int>>,cmp> heap;
        vector<string> ret;

        for(int i = 0; i < words.size(); ++i)
            hash[words[i]]++;
        
        for(auto e : hash)
        {
            heap.push(e);
            if(heap.size() > k)
                heap.pop();
        }

        while(k--)
        {
            string t = heap.top().first;
            ret.push_back(t);
            heap.pop();
        }
        reverse(ret.begin(),ret.end());

        return ret;
    }   
};