【优先级队列】前K个高频单词 && 数据流的中位数

输入: words = ["i", "love", "leetcode", "i", "love", "coding"], k = 2
输出: ["i", "love"]
解析: "i" 和 "love" 为出现次数最多的两个单词，均为2次。
    注意，按字母顺序 "i" 在 "love" 之前。

输入: ["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"], k = 4
输出: ["the", "is", "sunny", "day"]
解析: "the", "is", "sunny" 和 "day" 是出现次数最多的四个单词，
    出现次数依次为 4, 3, 2 和 1 次。

struct compare
{
    bool operator()(pair<string, int>& p1, pair<string, int>& p2)
    {
        // 特殊判断一下次数相等的情况
        if(p1.second == p2.second)
            return p1.first < p2.first; // 注意细节，字典顺序是从低到高，所以字典要搞个大堆才行，和频次相反
        return p1.second > p2.second;
    }
};

class Solution {
public:
    vector<string> topKFrequent(vector<string>& words, int k) {
        // 先统计每个单词出现次数
        unordered_map<string, int> hash;
        for(auto& word : words)
            hash[word]++;

        // 将哈希表内容按topk模式进行处理，使用小根堆
        priority_queue<pair<string, int>, vector<pair<string, int>>, compare> heap;
        for(auto& e: hash)
        {
            heap.push(e);

            if(heap.size() > k)
                heap.pop();
        }

        // 将堆中元素取出
        vector<string> str;
        while(!heap.empty())
        {
            str.push_back(heap.top().first);
            heap.pop();
        }

        reverse(str.begin(), str.end()); // 别忘了最后是从大到小排序，所以要逆序一下
        return str;
    }
};

输入
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]
输出
[null, null, null, 1.5, null, 2.0]

解释
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1);    // arr = [1]
medianFinder.addNum(2);    // arr = [1, 2]
medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2)
medianFinder.addNum(3);    // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0

class MedianFinder {
private:
    priority_queue<int> bigheap; // 大堆
    priority_queue<int, vector<int>, greater<int>> smallheap; // 小堆
public:
    MedianFinder() {}
    
    void addNum(int num) {
        // 如果大堆没有元素或者num小于等于大堆堆顶的话直接入大堆即可，否则就往小堆中插入
        if(bigheap.empty() || num <= bigheap.top())
            bigheap.push(num);
        else
            smallheap.push(num);
        
        // 插入完后判断两个堆的元素个数差距是否大于1
        if(bigheap.size() > smallheap.size() + 1)
        {
            // 如果大堆元素超出要求，则将大堆中堆顶元素放到小堆中去
            int top = bigheap.top();
            bigheap.pop();

            smallheap.push(top);
        }
        else if(bigheap.size() + 1 < smallheap.size())
        {
            // 如果小堆元素超出要求，则将小堆中堆顶元素放到大堆中去
            int top = smallheap.top();
            smallheap.pop();

            bigheap.push(top);
        }
    }
    
    double findMedian() {
        // 如果是奇数的话直接取元素个数多的堆的堆顶返回即可！
        if(bigheap.size() > smallheap.size())
            return bigheap.top();
        else if(bigheap.size() < smallheap.size())
            return smallheap.top();

        return (bigheap.top() + smallheap.top()) / 2.0; // 如果两个堆的元素总和为偶数，那么取两个堆的堆顶元素的平均值
    }
};

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