深度解析之算法之优先级队列（堆）

75.最后一块石头的重量

题目链接 有一堆石头，每块石头的重量都是正整数。

每一回合，从中选出两块 最重的 石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

• 如果 x == y，那么两块石头都会被完全粉碎；
• 如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。

最后，最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下，就返回 0。

示例：

输入：[2,7,4,1,8,1] 输出： 1 解释： 先选出 7 和 8，得到 1，所以数组转换为 [2,4,1,1,1]， 再选出 2 和 4，得到 2，所以数组转换为 [2,1,1,1]， 接着是 2 和 1，得到 1，所以数组转换为 [1,1,1]， 最后选出 1 和 1，得到 0，最终数组转换为 [1]，这就是最后剩下那块石头的重量。

提示：

• 1 <= stones.length <= 30
• 1 <= stones[i] <= 1000

class Solution

{

public:

    int lastStoneWeight(vector<int>& stones)

    {

        //创建一个大根堆

        priority_queue<int>heap;//默认是大堆

  

        //将所有的元素都丢到堆中

        for(auto x:stones)heap.push(x);//将元素入堆

  

        while(heap.size()>1)//如果此时堆中的个数大于1的话，那么我们就拿出两个进行碰撞

        {

            int a=heap.top();

            heap.pop();//删除第一块石头

            int b=heap.top();

            heap.pop();//删除第二块石头

  

            //如果两个石头都是相同的话，那么我们是不需要拿回任何的石头的

            //所有这里我们只需要处理不相同的情况

            if(a>b)heap.push(a-b);//将两者的差放到堆中

        }

        return heap.size()?heap.top():0;//如果堆中存在数据的话，那么我们将堆中的堆顶返回就行了，没有数据的话就返回0

    }

};

76.数据流中的第 K 大元素

题目链接 设计一个找到数据流中第 k 大元素的类（class）。注意是排序后的第 k 大元素，不是第 k 个不同的元素。

请实现 KthLargest 类：

• KthLargest(int k, int[] nums) 使用整数 k 和整数流 nums 初始化对象。
• int add(int val) 将 val 插入数据流 nums 后，返回当前数据流中第 k 大的元素。

示例 1：

输入： [“KthLargest”, “add”, “add”, “add”, “add”, “add”] [ [3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]

输出：[null, 4, 5, 5, 8, 8]

解释：

KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]); kthLargest.add(3); // 返回 4 kthLargest.add(5); // 返回 5 kthLargest.add(10); // 返回 5 kthLargest.add(9); // 返回 8 kthLargest.add(4); // 返回 8

示例 2：

输入： [“KthLargest”, “add”, “add”, “add”, “add”] [ [4, [7, 7, 7, 7, 8, 3]], [2], [10], [9], [9]]

输出：[null, 7, 7, 7, 8]

解释：

KthLargest kthLargest = new KthLargest(4, [7, 7, 7, 7, 8, 3]); kthLargest.add(2); // 返回 7 kthLargest.add(10); // 返回 7 kthLargest.add(9); // 返回 7 kthLargest.add(9); // 返回 8

提示：

• 0 <= nums.length <= 104
• 1 <= k <= nums.length + 1
• -104 <= nums[i] <= 104
• -104 <= val <= 104
• 最多调用 add 方法 104 次

这种就是TopK问题 用堆解决这个问题的时间复杂度是nlogn 快速选择算法时间复杂度是o(n)，但是数据一大就不行了

所以我们这里使用堆进行解决 1.创建一个大小为k的堆，大根堆or小根堆 2.循环 1.依次进堆 2.判断堆的大小是否超过k

如果堆的大小超过了 k，就弹出堆顶元素。这样，堆中的元素个数始终保持在 k 个，并且堆顶元素始终是当前流中第 k 大的元素。

class KthLargest

{

    //创建一个大小为k的小根堆

    priority_queue<int,vector<int>,greater<int>>heap;//加上greater<int>让堆变成小根堆

    int _k;//表示堆的大小

public:

    KthLargest(int k, vector<int>& nums)

    {

        _k=k;

        for(auto x:nums)

        {

            heap.push(x);//让数据进到堆中

            if(heap.size()>_k)heap.pop();//如果我们的堆中的数据大于k的话，我们就进行堆顶删除的操作

        }

    }

    int add(int val)

    {

        heap.push(val);//让新来的这个元素进堆

        if(heap.size()>_k)heap.pop();

        //当执行了上面的操作之后，此时的堆顶就是我们第K大的元素了

        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);

 */

77.前K个高频单词(不理解)

题目链接 给定一个单词列表 words 和一个整数 k ，返回前 k 个出现次数最多的单词。

返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率， 按字典顺序 排序。

示例 1：

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

示例 2：

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

注意：

• 1 <= words.length <= 500
• 1 <= words[i] <= 10
• words[i] 由小写英文字母组成。
• k 的取值范围是 [1, **不同** words[i] 的数量]

进阶： 尝试以 O(n log k) 时间复杂度和 O(n) 空间复杂度解决。

下面的代码是之前 学习优先级队列的时候做的

class Solution {

public:

    vector<string> topKFrequent(vector<string>& words, int k)

    {

        //按照次数进行比较

        //仿函数

        struct Compare

        {

            //比较两个键值对 kv1 和 kv2

            bool operator()(const pair<string,int>&kv1,const pair<string,int>&kv2)

            {

                return kv1.second>kv2.second||//次数大的在前面

                (kv1.second==kv2.second&&kv1.first<kv2.first);//次数相等的时候我们期望字典数小的在前面

            }

        };

        //统计处次数

        //使用 map 记录单词的频率

        map<string,int>countMap;

        //遍历输入单词列表 words，每遇到一个单词，就增加它在 countMap 中对应的计数值。

        for(auto&str:words)

        {

            countMap[str]++;

        }

  

        //sort是不能对map进行排序的

        //利用迭代器区间进行初始化操作

  

        //我们将这个map中的数据存储在vector中，利用迭代器

        //map 是有序的，但不支持直接排序。

        //将 map 的内容通过迭代器范围转换为一个 vector，以便后续对 vector 进行排序。

        vector<pair<string,int>>v(countMap.begin(),countMap.end());

  

        //sort默认是升序，我们期望排降序,但是是不稳定的，

        //stable_sort就是稳定的

        //使用 stable_sort 对 vector 进行排序，保证当两个单词频率相同时，按字典序排序

        sort(v.begin(),v.end(),Compare());//然后进行排序的操作

  

        //创建一个结果向量 retv，从排序后的 vector 中取出前 k 个单词（即频率最高的单词

        vector<string>retv;

        for(size_t i=0;i<k;++i)

        {

            retv.push_back(v[i].first);

        }

        return retv;

    }

};

  

/*

统计频率：

countMap = { "i": 2, "love": 2, "leetcode": 1, "coding": 1 }

排序后：

v = [("i", 2), ("love", 2), ("coding", 1), ("leetcode", 1)]

取前 2 个：

结果为 ["i", "love"]。

*/

  

//std::sort(起始迭代器, 结束迭代器, 比较器);

但是我们这里的解法就是利用堆来解决TopK问题 1.预处理一下原始的字符串数组： 用一个哈希表，统计一下每一个单词出现的频次 2.先创建一个大小为k的堆 频次：小根堆 字典序（频次相同的时候）：大根堆

3.循环 1.让元素依次进堆 2.判断

4.提取结果

按照频次的话，创建的是一个小根堆 按照字典顺序来的话，创建的是一个大根堆

class Solution

{

    typedef pair<string,int> PSI;//PSI 是一个 pair<string, int> 类型，代表单词及其对应的频率。string 表示单词，int 表示该单词出现的次数。

    struct cmp//比较函数

    {

        bool operator()(const PSI&a,const PSI&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)

    {

        //1.统计一下每一个单词的频次

        unordered_map<string,int>hash;

        for(auto&s:words)hash[s]++;

  
  

        //2.创建一个大小为k的堆

        priority_queue<PSI,vector<PSI>,cmp>heap;

  
  

        //3.TopK的主逻辑

        for(auto& psi:hash)

        {

            //依次将hash中的内容拿出来

            heap.push(psi);//放到堆中

            if(heap.size()>k)heap.pop();//如果此时堆中的元素个数大于k的话，那么我们就让头删，这样，第k大的单词就在堆顶了

        }

  

        //4.提取结果

        vector<string> ret(k);//初始化为k个大小

        for(int i=k-1;i>=0;i--)//循环k次

        {

            ret[i]=heap.top().first;//这里我们只需要堆顶元素中的string，就是这个单词

            heap.pop();

        }

        return ret;

    }

};

这段代码的功能是找到给定单词列表 words 中出现频率最高的 k 个单词，并返回它们。我们通过使用一个堆来保持频率最高的 k 个单词，堆的大小始终保持为 k，确保在遍历完所有单词后，堆顶就是第 k 高频的单词。

详细分析：

1. typedef pair<string, int> PSI;

• 定义一个类型别名：PSI 是一个 pair<string, int> 类型，代表单词及其对应的频率。string 表示单词，int 表示该单词出现的次数。

2. struct cmp

• 这是一个自定义的比较函数，用来在堆中进行元素的排序。堆中存储的是 PSI 类型的元素，PSI 类型是由单词和频次构成的 pair<string, int>。
• operator()：这个函数定义了堆的排序规则。
  • 如果两个元素的频率相同（即 a.second == b.second），那么按照字典序排列（即按 a.first < b.first 排序），这相当于让字典序较小的单词排在堆的前面。
  • 如果两个元素的频率不同，那么就根据频率来排序（a.second > b.second），频率较高的单词会排在堆的前面。

  这个比较函数会被传给 priority_queue，用来控制堆中的排序行为。

3. vector<string> topKFrequent(vector<string>& words, int k)

这是主函数，接受一个单词列表 words 和一个整数 k，返回频率最高的 k 个单词。

1) 统计每个单词的频次

unordered_map<string, int> hash;
for (auto &s : words) hash[s]++;

• unordered_map<string, int>：我们使用一个 unordered_map 来统计每个单词的出现次数。键是单词，值是该单词出现的次数。
• 遍历 words 数组，对于每个单词，hash[s]++ 会把该单词的频次增加 1。

2) 创建一个大小为 k 的堆

priority_queue<PSI, vector<PSI>, cmp> heap;

• 这里我们声明了一个优先队列 heap，堆的元素类型是 PSI，也就是 pair<string, int> 类型。
• cmp 是我们之前定义的比较函数，用于指定堆的排序规则。
• 通过这个堆，我们始终保持堆中存储着频率最高的 k 个单词及其频率。

3) 填充堆，并保持堆的大小为 k

for (auto& psi : hash)
{
    heap.push(psi); // 将单词及其频率放入堆中
    if (heap.size() > k) heap.pop(); // 如果堆中的元素超过k个，弹出堆顶元素
}

• 遍历 hash 中的每个元素（即每个单词及其频次）。
• 每次将一个单词及其频次加入堆中。如果堆的大小超过了 k，我们就弹出堆顶元素。由于我们的堆是按照频率进行排序的，所以堆顶元素是频率最小的那个。这样，堆中的元素始终保持 k 个最频繁的单词。

4) 提取堆中的单词

vector<string> ret(k); // 初始化一个大小为k的返回结果向量
for (int i = k - 1; i >= 0; i--) // 从堆顶开始提取k个单词
{
    ret[i] = heap.top().first; // 取出堆顶元素的单词部分
    heap.pop();
}
return ret;

• 创建一个大小为 k 的返回结果向量 ret，用于存储返回的 k 个单词。
• 我们需要将堆中的单词按频率从高到低排序，因此我们从堆顶开始提取单词，并将它们依次放入 ret 中。
• heap.top().first 访问堆顶元素的 first 成员，也就是单词本身。
• 提取完堆顶元素后，我们用 heap.pop() 删除堆顶元素，直到提取出所有 k 个单词。

总结

• 该算法通过 unordered_map 来统计每个单词的频次，使用自定义比较函数的堆来维护 k 个频率最高的单词。通过堆来保证我们始终能够找到频率最高的 k 个单词。
• 时间复杂度：
  • 统计单词频次的时间复杂度是 O(n)，其中 n 是单词的个数。
  • 将单词加入堆的时间复杂度是 O(n log k)，因为每次向堆中添加一个元素的时间复杂度是 O(log k)，我们要对 n 个元素进行操作。
  • 最后提取堆中元素的时间复杂度是 O(k log k)，因为我们要提取 k 个元素。
• 所以，总的时间复杂度是 O(n log k)，其中 n 是单词数量，k 是需要返回的单词数量。

cmp 是一个自定义的比较函数，用于定义堆（priority_queue）的排序规则。在这段代码中，cmp 用于实现对堆中元素的排序方式，使得堆能够按照特定的规则维护顺序。

1. 堆排序的基本概念

• 默认情况下，C++ 的 priority_queue 是大根堆（max-heap）。即，堆顶元素是当前堆中最大的元素。
• 通过定义比较函数（cmp），我们可以控制堆是大根堆（默认）、小根堆，或者按照其他自定义的规则进行排序。

在这段代码中，我们使用 cmp 来控制堆中的元素（即 pair<string, int> 类型的元素）排序的方式，特别是为了保持频率最高的 k 个单词。

2. cmp 比较函数的作用

cmp 是一个结构体，定义了一个重载的 operator()，它控制了堆元素的排序方式。

struct cmp {
    bool operator()(const PSI &a, const PSI &b) {
        if (a.second == b.second) { // 如果频率相同
            return a.first < b.first; // 按字典序升序排列
        }
        return a.second > b.second; // 否则，按频率降序排列
    }
};

详细解释：

1. a.second == b.second
   • a 和 b 都是 PSI 类型，也就是 pair<string, int>，a.first 是单词，a.second 是频率。
   • a.second 和 b.second 分别是单词 a 和 b 的频率。
   • 这个条件判断用来比较两个单词的频率。如果两个单词的频率相同（a.second == b.second），则进入字典序比较。
2. a.first < b.first
   • 如果两个单词的频率相同，就按照单词本身进行字典序的升序排列。a.first < b.first 是按字典序升序排列两个单词。
   • 举个例子，如果有两个单词 "apple" 和 "banana"，它们的频率相同，那么 "apple" 会排在 "banana" 前面。
3. a.second > b.second
   • 如果两个单词的频率不同，则返回 a.second > b.second，这意味着频率较高的单词会排在前面，即大根堆的行为。也就是说，频率较高的单词会在堆的顶部。

3. 如何影响堆的行为？

• 频率较高的单词会优先出现在堆顶，因此每次我们向堆中插入元素时，堆会自动按照这个规则调整堆的位置。
• 如果两个单词的频率相同，那么根据字典序来排列。在字典序上排在前面的单词（字母较小的单词）会排在堆的前面。

4. 堆如何使用 cmp 排序？

• priority_queue<PSI, vector<PSI>, cmp> heap; 这里的 cmp 就是自定义的排序规则，确保堆的排序符合我们的要求。堆中的元素会根据频率从大到小排列，频率相同的元素则按字典序升序排列。

5. 实际效果

在 topKFrequent 函数中，当我们将单词及其频次放入堆时，堆的排序规则会保证：

• 堆的大小最多为 k，且堆顶元素是当前频率最小的单词。
• 在所有频率相同的单词中，字典序较小的单词会被放在堆顶。

最后，我们提取堆中的元素时，堆顶就是当前频率第 k 高的单词，返回结果时就是我们需要的前 k 个频率最高的单词。

总结：

• cmp 的作用是通过自定义的排序规则，确保堆中的元素按照频率从高到低排序。如果频率相同，则按字典序升序排列。
• 这个比较函数确保了 priority_queue 在保持堆结构的同时，能够实现我们所需的排序规则，即频率最高的单词排在前面，频率相同的单词按字典序排列。

78.数据流的中位数

题目链接 中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。

• 例如 arr = [2,3,4] 的中位数是 3 。
• 例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5 。

实现 MedianFinder 类:

• MedianFinder() 初始化 MedianFinder 对象。
• void addNum(int num) 将数据流中的整数 num 添加到数据结构中。
• double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 10-5 以内的答案将被接受。

示例 1：

输入 [“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

提示:

• -105 <= num <= 105
• 在调用 findMedian 之前，数据结构中至少有一个元素
• 最多 5 * 104 次调用 addNum 和 findMedian

动态的维护这批数的中位数

暴力解法 解法一：直接sort，每次调用add的时候时间复杂度是nlogn，会超时的

解法二：插入排序的思想，也是会超时的

解法三：大小堆来维护数据流的中位数

左边的数放到大根堆中，那么这个大根堆中的最右边的就是我们左边区域最大的数了 那么右边是小根堆，那么最左边的就是最大，最右边的就是最小的

class MedianFinder

{

    //即使没有显式地写出 vector<int>，priority_queue 仍然会使用 vector<int> 来存储堆中的元素。这样做的原因是 vector 是一个高效的动态数组，非常适合用来作为堆的底层容器。

    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())//如果左堆是空的，或者num小于堆顶的数，那么就放左堆

            {

                left.push(num);//我们直接放就行了，就能保证左边的堆大于等于右边的堆

            }

            else//放右堆了

            {

                right.push(num);//将这个数放到右边堆

                left.push(right.top());//需要让右边堆的堆顶的数据放到左边堆里面去

                right.pop();//删除堆顶的数

  

            }

  

        }

        else//左右两个堆的元素个数不同

        {

            if(num<=left.top())//如果这个数小于左堆最大值的话

            {

                left.push(num);//那么我们就将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;//我们因为函数是返回的是一个doble类型的数，所以我们这里除以2.0

        }

        else//左边堆的数是多的

        {

            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();

 */

左边是大根堆，堆顶是最大的数，右边是小根堆，堆顶是最小的数

我们需要时刻维护两个堆中的数据的个数吗，不然的话就会失去平衡了 假设我们依次插入以下数字：1, 5, 2, 8, 3

1. 插入 1：left = [1]，right = []。
   • 此时大根堆 left 中的堆顶元素就是 1，它是中位数。
2. 插入 5：left = [1]，right = [5]。
   • 中位数是 (1 + 5) / 2 = 3，因为两个堆大小相等。
3. 插入 2：left = [2, 1]，right = [5]。
   • 中位数是 2，因为大根堆 left 中的堆顶元素是中位数。
4. 插入 8：left = [2, 1]，right = [5, 8]。
   • 中位数是 (2 + 5) / 2 = 3.5，因为两个堆大小相等。
5. 插入 3：left = [2, 1, 3]，right = [5, 8]。
   • 中位数是 3，因为大根堆 left 中的堆顶元素是中位数。