算法思想总结：优先级队列

一、最后一块石头的重量

. - 力扣（LeetCode）

我们每次都要快速找到前两个最大的石头进行抵消，这个时候用优先级队列（建大堆）,不断取堆顶元素是最好的！每次删除堆顶元素后，可以自动调整，时间复杂度是logN。

class Solution {
public:
    int lastStoneWeight(vector<int>& stones) 
    {
        //建立优先级队列  大堆
       priority_queue<int> heap;
       for(auto&num:stones) heap.push(num);
       while(heap.size()>1)
       {
        int x=heap.top();
        heap.pop();
        int y=heap.top();
        heap.pop();
        if(x>y) heap.push(x-y); 
       }
       return heap.size()?heap.top():0;//不为空，就返回堆顶元素，为空，就返回0
    }
};

二、数据流中的第K大元素

. - 力扣（LeetCode）

（1）在学习分治专题的时候，我们知道topK问题可以用优先级队列去解决也可以用快速排序的三路划分去解决，并且快速排序反而会更优秀一点，那优先级队列的优势究竟体现在哪里呢？？其优势体现在可以不断地去取用堆顶元素或者是加入元素的时候都可以通过用logN的时间复杂度进行调整，而前期建堆也仅仅是N*logN的时间复杂度，而快速排序的三路划分则是一次性的N的时间复杂度，所以长期优先级队列收益高，短期收益快速排序的三路划分收益高。

class KthLargest {
    priority_queue<int,vector<int>,greater<int>> heap;//仿函数
    int k;   //创建一个大小为k的小根堆 堆顶始终是第k大的元素
    //用快速排序算法可以是O（N）的复杂度，但是如果是要频繁去获取，就很显然得依靠优先级队列
public:
    KthLargest(int _k, vector<int>& nums) 
    {
        k=_k; 
       for(auto &val:nums) 
       {
        heap.push(val);
       if(heap.size()>k) heap.pop();//入堆的同时进行向上调整
       }
    }
    int add(int val) 
    {
       heap.push(val);
       if(heap.size()>k)heap.pop();//可能我插入的时候堆里啥也没有
       return heap.top();
    }
};

三、数据的中位数

. - 力扣（LeetCode）

策略1：存在数组中用sort去排序 —— add（NlogN） find(1)

策略2：还是存在数组中，利用插入排序的思想，因为插入之间就已经是有序的了，所以新元素插入时的时间复杂度是插入排序的最好情况O（N） ——add(N) find(1)

策略3：优先级队列大小堆维护中位数 add(logN) find(1)

设计思路：

1、建立left为大根堆，right为小根堆

2、我们的add控制始终保持left的数量要么和right相等，要么比right多一个，为了能够满足在O（1）的复杂度内完成找到中位数的任务，我们希望当left多一个的时候，left堆顶的元素就是中位数，而当left和right相等的时候，中位数就是两个堆的堆顶元素的平均值。

3、为了达到这个目的，我们在时刻控制left和right的数量的同时，一定要保证left里面的元素是小于等于right里面的元素的，所以add要分两种情况去讨论：

情况1：当两个堆的元素个数相等的时候

（1）如果left为空，或者是add的元素比left的堆顶元素小，那么就让该元素直接进left

（2）如果add的元素比left的堆顶元素大，那么他也有可能会比right的元素大，所以我们必须要将这个元素丢到right中，但是直接丢就会破坏规则，所以我们要先将add的元素丢到right中进行调整，然后再将right的堆顶元素丢到left中去，保持left和right的数量关系。（注意，这里的先后顺序很重要，我们不能先将right的堆顶元素丢到left中，然后再将add丢到right中进行调整，因为我们只是知道这个数比left的堆顶元素大，但是他是比right的堆顶元素大还是小我们不得而知，必须要通过他自己的向下调整去选出来）

情况2：当left的元素比right多一个的时候

（1）如果add的元素比left的堆顶元素大，这个时候无脑进右边就行了。

（2）如果add的元素比left的堆顶元素小，这个时候我们也得把add的元素丢到left中，然后为了保持数量关系，将调整过后的left的堆顶元素移到right中即可。

细节处理：

1、我们在比较的时候始终实用left的元素进行比较，因为左边不为空的时候右边也可能为空，所以我们如果不用left去比较而是用right去比较，那么还需要多考虑一种边界情况。

2、虽然我们add的都是int类型，但是当两个堆的元素个数相同的时候，我们去取两个堆顶元素取平均值的，而平均值是有可能会出现小数的，所以如果我们还用int的话可能会造成小数点丢失，所以我们在/2的时候变成/2.0,这样结果就会被强转成double；

class MedianFinder {
public:
    MedianFinder() {} //默认初始化不管了
    void addNum(int num) {
       //分类讨论 m==n或者m==n+1
       size_t m=left.size(),n=right.size();
       if(m==n) //m==n->m==n+1
       {
           //如果我比左边的堆顶小，或者是为空，我就进左边
           if(m==0||num<=left.top()) left.push(num);
           else //如果我比堆顶大,那我要进右边，然后把右边的移过来
           {
             right.push(num);
             left.push(right.top());
             right.pop();
           }
       }
       else // m==n+1 ->m==n
       {
          //如果我比左边的小，直接进右边即可
          if(num <= left.top()) 
          {
             left.push(num);
             right.push(left.top());
             left.pop(); 
          }
          else //如果我比左边的大 无脑进右边 
          right.push(num);
       }
    }
    
    double findMedian() 
    { //我们的策略是 m==n 返回堆顶平均值  如果m==n+1 返回左边的堆顶
      if(left.size()>right.size()) return left.top();
      else return (left.top()+right.top())/2.0;
    }
    private:
         priority_queue<int> left;//左边是大根堆
         priority_queue<int,vector<int>,greater<int>> right;///右边是小根堆
};

四、前K个高频词汇

. - 力扣（LeetCode）

该题是一道非常经典的OJ题，在哈希表章节中介绍了四种解法，运用stl中的不同容器去解决。

算法思想总结：哈希表-CSDN博客

class Solution {
public:
   typedef pair<string,int> PSI;
    struct compare//要注意仿函数要+const修饰，否则可能编译不过
     {
        bool operator()(const PSI&kv1,const PSI&kv2) const
        {
            if(kv1.second==kv2.second) return kv1.first<kv2.first;
            return kv1.second>kv2.second;
        }
     };
    vector<string> topKFrequent(vector<string>& words, int k) 
    {
        unordered_map<string,int> countmap;//计数
        for(auto&s:words) ++countmap[s];
        //丢到优先级队列里
        priority_queue<PSI,vector<PSI>,compare> heap;
        for (auto& it : countmap) {
            heap.push(it);
            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;
    }
};