深度剖析优先级队列：堆的搭建至解题策略全方位解读

深度解析优先级队列：堆的构建到解题策略的全面解读

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

文章目录

• 一、铺垫知识
• • 1.1 堆排序（Heap Sort）
  • 1.2 快速选择（QuickSelect）算法解Top K问题
  • 3.Tok问题中，大根堆与小根堆的使用场景
  • 1046. 最后一块石头的重量
  • 703. 数据流中的第K大元素
  • 692. 前K个高频单词
  • 295. 数据流的中位数

本专题借助优先级队列解决问题。首先需了解堆与快速选择算法解Top K问题，明确大根堆与小根堆的适用场景及选择依据。

一、铺垫知识

1.1 堆排序（Heap Sort）

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

可参考文章：理解堆的特性与应用

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

用选择排序解Top K（Tok）问题时，无需全排序，仅需K次选择找第K大（小）元素
将上述步骤整合
快速选择排序整合
若用选择排序解Top K问题，仅需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> pq;
        for (auto x : stones) pq.push(x);
        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() ? pq.top() : 0;
    }
};

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

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

【算法思路】

此题为Top K问题，用小根堆。插入新元素时，若堆大小超K，移除堆顶（最小）。插入时，堆自动调整，堆顶为K大元素中最小。若插入元素大于堆顶，替换；否则不变。动态维护第K大。

【代码实现】

class KthLargest {
public:
    priority_queue<int, vector<int>, greater<int>> pq;
    int k;
    KthLargest(int k, vector<int>& nums) {
        this->k = k;
        for (auto x : nums) {
            pq.push(x);
            if (pq.size() > k) pq.pop();
        }
    }

    int add(int val) {
        pq.push(val);
        if (pq.size() > k) pq.pop();
        return pq.top();
    }
};

692. 前K个高频单词

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

【算法思路】

本题用堆解Top K，需选堆结构。有两排序：频次用小根堆，保证堆顶是K个中频次最低；字典序（频次同）用大根堆，保证同频次降序。因字典序是频次子集，比较函数中加if实现多条件。结果倒序，用小根堆维护前K高频。

【代码实现】

class Solution {
public:
    using PSI = pair<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;
        }
    };

    vector<string> topKFrequent(vector<string>& words, int k) {
        unordered_map<string, int> cnt;
        for (auto& str : words) cnt[str]++;
        priority_queue<PSI, vector<PSI>, Cmp> pq;
        for (auto& p : cnt) {
            pq.push(p);
            if (pq.size() > k) pq.pop();
        }
        vector<string> res(k);
        for (int i = k - 1; i >= 0; i--) {
            res[i] = pq.top().first;
            pq.pop();
        }
        return res;
    }
};

295. 数据流的中位数

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

【算法思路】

数据量大时前两法可能超时，用大小堆维护。根据m==n和m>n（m=n+1）分类，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.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;
        } else {
            return left.top();
        }
    }
};

【细节】

访问left.top()前检查堆非空，如条件left.empty() || num <= left.top()。

快来和小二开启算法之旅！关注我，一同破解算法难题，探索实用有趣知识，开启编程冒险！