【优选算法 | 优先级队列】从堆实现到解题框架：彻底搞懂优先级队列

优先级队列（Priority Queue），本质上是一个支持动态插入与按优先级弹出操作的堆结构，是处理这类问题的强力工具。
本文将从底层的堆实现出发，逐步构建出优先级队列的完整解题框架，并结合高频
题目，帮助你真正掌握它在算法实战中的运用。

🌈个人主页：是店小二呀
🌈C/C++专栏：C语言\ C++
🌈初/高阶数据结构专栏： 初阶数据结构\ 高阶数据结构
🌈Linux专栏： Linux
🌈算法专栏：算法
🌈Mysql专栏:Mysql

🌈你可知:无人扶我青云志 我自踏雪至山巅

本专题利用优先级队列来解决问题。为此，我们首先需要了解如何使用堆和快速选择算法来解决 Tok 问题，并掌握大根堆与小根堆的适用场景及选择依据。

一、铺垫知识

1.1 堆排序（Heap Sort）

堆排序使用 最大堆（Max Heap） 或 最小堆（Min Heap） 来实现排序。

具体可以参考这篇文章:理解堆的哇塞大碗大碗吗。 ， ，/，/ 发 的特性与应用

1.2 快速选择（QuickSelect）算法解决 Top K 问题

如果你使用 选择排序 来解决 Top K（Tok）问题，实际上不需要对整个数组进行完整排序，而是只运行 K 次选择过程 来找到 第 K 大（或 K 小）元素。

具体可以参考这篇文章:七大常见排序

3.在Tok问题，什么时候使用大根堆和小根堆？

• 大根堆（Max Heap）：
• 用于获取最大元素或 Top K 最小元素（维持 K 个最小元素，堆顶最大）。
• 示例：找 前 K 小（维护大小为 K 的大根堆）。
• 小根堆（Min Heap）：
• 用于获取最小元素或 Top K 最大元素（维持 K 个最大元素，堆顶最小）。
• 示例：找 前 K 大（维护大小为 K 的小根堆）。

1046. 最后一块石头的重量

【题目】：1046. 最后一块石头的重量

【算法思路】

利用堆的特性，反复取出当前最大值和次大值进行碰撞处理，然后将结果重新插入堆中。

【代码实现】

class Solution {
public:
    int lastStoneWeight(vector<int>& stones) 
    {
        int n = stones.size();
        
        priority_queue<int> head;
        for(auto x: stones) head.push(x);
        
        while(head.size() > 1)
        {
            int x = head.top(); head.pop();
            int y = head.top(); head.pop();
            if(x > y) head.push(x - y);
        }
        return head.size() ? head.top(): 0;
    }
};

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

【题目】：703. 数据流中的第 K 大元素

【算法思路】

该题主要考察 Top K 问题的处理方法。为了查找第 K 大元素，我们使用小根堆。当插入新元素时，如果堆的大小超过 K，就会移除堆顶元素（即最小值）。

每次插入时，堆会自动调整，保持堆顶为当前 K 个最大元素中的最小值。如果插入的元素大于堆顶，则替换堆顶元素；如果小于堆顶，则保持堆不变。通过这种方式，堆会动态维护第 K 大元素。

【代码实现】

class KthLargest {
public:

    priority_queue<int, vector<int>, greater<int>> heap;
    int _k;
    KthLargest(int k, vector<int>& nums) 
    {
        _k = k;
        for(auto 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();
    }
};

692. 前K个高频单词

【题目】：692. 前K个高频单词

【算法思路】

本题明确要求使用堆来解决 Top K 问题，接下来我们分析其算法思路

要使用堆来解决 Top K 问题，需要根据题目要求选择合适的堆结构。这里有两种排序策略：
频次:小根堆

• 按频次排序：使用小根堆，确保堆顶始终是当前 K 个元素中频次最低的。
• 按字典序排序（当频次相同时）：使用大根堆，保证相同频次下按字典序降序排列。

由于字典序排序是频次排序的子集，我们可以在比较函数中添加 if 语句，灵活实现多条件排序。最终结果需要倒序遍历，因为答案要求按照单词出现频率从高到低排序，因此我们使用小根堆来维护前 K 个高频元素。

【代码实现】

class Solution {
public:
    typedef pair<string, int> PSI;
    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;
        }
    };

    vector<string> topKFrequent(vector<string>& words, int k) 
    {
        //1.统计单词出现次数
        unordered_map<string, int> hash;
        for(auto& str : words) hash[str]++;

        //2.创建一个大小为 k 的堆(存储频率)
        priority_queue<PSI, vector<PSI>, Cmp> heap;

        //3.Tok逻辑
        for(auto& psi : hash)
        {
            heap.push(psi);
            if(heap.size() > k)
                heap.pop();
        }

        //4.提取结果
        vector<string> ret(k);
        for(int i = k - 1; i >= 0; i--)
        {
            ret[i] = heap.top().first;
            heap.pop();
        }

        return ret;
    }
};

295. 数据流的中位数

【题目】：295. 数据流的中位数

【算法思路】

由于数据量庞大，前两种解法可能会超时。接下来介绍一种优化解法，虽然不太容易直接想到，但学会后会觉得非常简单。这个方法与栈用于括号匹配或出栈队列类似，思路是用大小堆来维护数据流的中位数。遇到类似问题时，可以考虑使用这种思路。

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

根据准则 m == n 和 m > n (m == n + 1)，我们根据 num 的值进行分类讨论。当 num < x 时，放入大根堆，否则放入小根堆。然后根据这两个准则和两个堆的数量关系，进行适当的调整和维护。

【代码实现】

class MedianFinder {
public:

    priority_queue<int> left;//大根堆
    priority_queue<int,vector<int>, greater<int>> right;//小根堆
    
    MedianFinder() 
    {
    }
    
    void addNum(int num) 
    {
        if(left.size() == right.size())
        {
            if(left.size() == 0 || num <= left.top()) left.push(num);
            else if(num > left.top())
            {
                right.push(num);
                left.push(right.top());
                right.pop();
            }
        }
        else
        {
            if(num <= left.top())
            {
                left.push(num);
                right.push(left.top());
                left.pop();
            }
            else if(num > left.top()) right.push(num);
        }
        
    }
    
    double findMedian() 
    {
        if(left.size() == right.size()) return ((left.top() + right.top()) / 2.0);
        else return left.top();
    }
};

【细节问题】

为了避免在访问 left.top() 时出现非法访问，我们应该首先检查 left 大根堆是否为空。具体来说，条件 left.size() == 0 || num <= left.top() 确保只有在堆非空且 num 小于等于堆顶元素时，才执行相关操作。

快和小二一起踏上精彩的算法之旅！关注我，我们将一起破解算法奥秘，探索更多实用且有趣的知识，开启属于你的编程冒险！