算法笔记（十一）——优先级队列(堆)

堆是一种二叉树的结构，有两种主要类型：最大堆和最小堆
下面附上之前写的两篇博客：
优先级队列(priority_queue）
数据结构堆（Heap）的实现

最后一块石头的重量

题目：最后一块石头的重量

思路

• 创建一个大根堆priority_queue<int> pq;默认情况下是大根堆，将所以石头加入到堆中
• 用一个循环处理，直至堆中元素剩余元素个数小于等于1
• 依次取出堆顶元素x,y其中x >= y
• 若 x = y ，则pop掉两元素；
• 若x > y，则pop掉两元素，之后将x - y，push进堆
• 循环结束后，若剩一个元素，即为其重量；若堆为空，则返回0

C++代码

class Solution 
{
public:
    int lastStoneWeight(vector<int>& stones) 
    {
        priority_queue<int> pq; 
        for(auto e : stones) 
            pq.push(e);
        
        while(pq.size() > 1) 
        {
            int x = pq.top();
            pq.pop();
            int y = pq.top();
            pq.pop();

            if (x > y)
                pq.push(x - y);   
        }

        return pq.size() == 0 ? 0 : pq.top();  
    }
};

数据流中的第 K 大元素

题目：数据流中的第 K 大元素

思路

• 经典topK问题
• 创建一个大小为k的堆
• 循环：依次进堆，判断堆的大小是否超过k

找的是第k大元素，维护一个大小为k的最小堆，保证堆中只有前 k大的元素

• 将新元素加入最小堆中，然后检查堆的大小是否超过k，如果超过则弹出堆顶元素
  最终返回当前堆顶元素，即为第 k大的元素
• 在 add 操作后始终保持堆中的元素为前 K 大的元素
• 而堆顶元素即为第k大的元素。

C++代码

class KthLargest 
{
    // 创建一个大小为 k 的小根堆
    priority_queue<int, vector<int>, greater<int>> heap;
    int _k;
public:
    KthLargest(int k, vector<int>& nums) 
    {
        _k = k;
        for(int& x : nums)
        {
            heap.push(x);
            if(heap.size() > k) 
                heap.pop();
        }
    }
    
    int add(int val) 
    {
        heap.push(val);
        if(heap.size() > _k) 
            heap.pop();

        return heap.top();
    }
};

/**
 * Your KthLargest object will be instantiated and called as such:
 * KthLargest* obj = new KthLargest(k, nums);
 * int param_1 = obj->add(val);
 */

前K个高频单词

题目：前K个高频单词

思路

• 经典topK问题
• 创建一个大小为k的堆
• 循环：依次进堆，判断堆的大小是否超过k

找出前k个出现次数最多的，所以整体我们建小堆
对比较函数按照要求实现，不能用库里的；
如果两个字符串出现频率相同，那么我们让两字符串中字典序较小的排在前面，否则我们让出现频率较高的排在前面
C++代码

class Solution 
{
    typedef pair<string, int> PSI;
    struct cmp
    {
        bool operator()(const PSI& x, const PSI& y)
        {
            if(x.second == y.second) return x.first < y.first;
            else return x.second > y.second;
        }
    };
public:
    vector<string> topKFrequent(vector<string>& words, int k) 
    {
        // 统计单词的频次
        unordered_map<string, int> hash;
        for(auto e:words) hash[e]++;
        // 创建一个大小为 k 的堆
        priority_queue<PSI, vector<PSI>, cmp> heap;
        
        for(auto&e:hash)
        {
            heap.push(e);
            if(heap.size() > k) heap.pop();
        }
        // 答案
        vector<string> ret(k);
        for(int i = k - 1; i >= 0; i--)
        {
            ret[i] = heap.top().first;
            heap.pop();
        }
        return ret;
    }
};

数据流的中位数

题目：数据流的中位数

思路

利用大小堆来维护数据流的中位数

• 初始化两个优先队列
• left 用于存放较小的一半元素（大根堆）
• right 用于存放较大的一半元素（小根堆）
  
• 个数为偶数时，大根堆元素个数m等于小根堆元素个数n，即m = n；
• 个数为奇数时，大根堆left多放一个，即m = n + 1
• x，y 分别为大根堆、小根堆堆顶元素

当add()添加元素时，我们按照下述方法维护两个堆

• 当m == n时，
• • num <= x || m == 0，num直接进入left堆
• • num > x ，num先进入right堆，再将right堆定元素放入left堆
• 当m == n + 1时，
• • num <= x，num直接进入left堆，再将left堆定元素放入堆right
• • num > x ，num直接进入right堆

C++代码

class MedianFinder 
{
    priority_queue<int> left;
    priority_queue<int, vector<int>, greater<int>> right;
public:
    MedianFinder() {}
    
    void addNum(int num) 
    {
        if(left.size()  == right.size())
        {
            if(left.empty() || num <= left.top()) 
                left.push(num);
            else
            {
                right.push(num);
                left.push(right.top());
                right.pop();
            }
        }
        else
        {
            if(num <= left.top())
            {
                left.push(num);
                right.push(left.top());
                left.pop();
            }
            else 
                right.push(num);
        }
    }
    
    double findMedian() 
    {
        if(left.size() == right.size()) 
            return (left.top() + right.top()) / 2.0;

        return left.top();
    }
};

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