C++ 优先级队列(大小根堆)OJ

Han同学

已于 2024-03-15 08:17:56 修改

阅读量1.3k

点赞数 22

分类专栏：基础算法文章标签： c++ 算法

于 2024-03-15 00:21:57 首次发布

本文链接：https://blog.csdn.net/m0_73800602/article/details/136607384

版权

文章介绍了如何使用小根堆解决TopK问题，如数据流中的第K大元素问题，以及利用大根堆和小根堆维护动态中位数。通过频次统计和堆排序策略，实现在数据流中高效查找和更新频繁单词和中位数。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

1、 1046. 最后一块石头的重量

思路：根据示例发现可以用大根堆(降序)模拟这个过程。

class Solution {
public:
    int lastStoneWeight(vector<int>& stones) {
        priority_queue<int> heap;
        for (auto s : stones)
            heap.push(s);
        while (heap.size() > 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;
    }
};

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

思路：TopK问题使用小根堆堆解决，priority_queue（默认大根堆）的第三个参数为greater<类型>即为小根堆。

class KthLargest {
public:
    int _k;
    priority_queue<int, vector<int>, greater<int>> heap;
    KthLargest(int k, vector<int>& nums) {
        _k = k;
        for (auto n : nums) {
            heap.push(n);
            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);
 */