【算法】堆与优先级队列

【ps】本篇有 4 道 leetcode OJ。

一、算法简介

二、相关例题

1）最后一块石头的重量

.1- 题目解析

.2- 代码编写

2）数据流中的第 K 大元素

.1- 题目解析

.2- 代码编写

3）前K个高频单词

.1- 题目解析

.2- 代码编写

4）数据流的中位数

.1- 题目解析

.2- 代码编写

一、算法简介

普通队列的特点是先进先出，元素在队尾入队，而从队首出队。优先级队列则不同，队列中的每个元素都被赋予了一个权值，权值较高的元素排在最前优先出队。它一般默认通过一个大根堆（即权值以从高到低排列）实现，表现为一个以 vector 为底层的完全二叉树。

优先级队列常与模拟算法一起出题。除了要掌握如何对优先级队列建大根堆或小根堆，还要能够不借助 STL 提供的优先级队列来自己实现堆这种数据结构，因为这是面试场上常考的（欲知堆的更多细节，请见【数据结构】树之二叉树）。

二、相关例题

1）最后一块石头的重量

1046. 最后一块石头的重量

.1- 题目解析

对于从一个序列中选出最大值，不难想到堆排序和优先级队列。我们可以将数组中的元素全部插入优先级队列中，然后依此从堆顶取两个元素进行“粉碎”，这两个元素其中一个一定是当前数组中最大的，另一个一定是次大的。如果它们两个相等，就不作处理，相当于两个都“粉碎”了；如果不相等，就将它们的差值入队......以此类推，直至优先级队列中没有元素或仅剩一个元素。

.2- 代码编写

class Solution {
public:int lastStoneWeight(vector<int>& stones) {priority_queue<int> heap;for(auto x:stones)heap.push(x);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）数据流中的第 K 大元素

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

.1- 题目解析

这是一道典型的 Top-K 问题，其解决方法有堆排序、基于快排的快速选择算法。尽管快速选择算法的时间复杂度为 O(n)，堆排序为 O(n*logK)，但面对海量数据时，快速选择算法的空间复杂度颇高，因此此处选用更优的堆排序来解题。

具体方式是，创建一个大小为 k 的堆，如果是找第 k 大（排降序）就创建小根堆，找第 k 小（排升序）就创建大根堆。然后将待排序的元素依此进堆，每次进堆都判断一下堆的大小是否超过 k，如此，堆顶存放的就一直是第 k 大或第 k 小的元素。

.2- 代码编写

class KthLargest {priority_queue<int,vector<int>,greater<int>> heap;//排降序建小根堆int _k;
public://显示的构造函数KthLargest(int k, vector<int>& nums) {_k=k;for(auto x:nums){//先将元素入堆进行排序heap.push(x);//堆的大小超过k，就把堆顶元素取出，只留下第k大的元素在堆顶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);*/

3）前K个高频单词

692. 前K个高频单词

.1- 题目解析

这也是一道典型的 Top-K 问题。在进行堆排序找到前 k 个高频单词之前，我们需要先对数组中的单词出现的频次进行统计，这样才能进行堆排序。

而特别的，一般情况下应按单词出现频率由高到低排序，此时应建小堆；当不同的单词有相同频次时，就要按字典序来排序，此时应建大堆。那么，我们就需要对建堆的排序函数进行特殊处理。

由于堆顶存放的是频次前 k 大中频次最小的单词，因此从堆顶依此取元素并插入到数组中的时候，需要将元素从后往前插入到数组中，或者从前往后插入，最终将数组逆序。

.2- 代码编写

class Solution {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;}};
public:vector<string> topKFrequent(vector<string>& words, int k) {//1.用哈希表统计频次unordered_map<string,int> hash;for(auto&s:words)hash[s]++;//2.建堆priority_queue<PSI,vector<PSI>,cmp> heap;for(auto& x:hash){heap.push(x);if(heap.size()>k)heap.pop();}//3.统计结果vector<string> ret(k);for(int i=k-1;i>=0;i--){ret[i]=heap.top().first;heap.pop();}return ret;}
};

4）数据流的中位数

295. 数据流的中位数

.1- 题目解析

要找到一个中位数，这个数据序列必须是有序的。我们可以将一个排好序的序列一分为二，将序列左边的所有元素放入大根堆里，将序列右边的所有元素放入小根堆里，如此，大根堆的堆顶就是序列左边的最大元素，小根堆的堆顶就说序列右边的最小元素，此时只要把这两个堆顶元素相加除以 2，就能得到整个序列的中位数了。

设 num 是一个待插入堆的元素，m 为序列左边的元素个数，n 为序列右边的元素个数，则：

.2- 代码编写

class MedianFinder {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()){left.push(num);}else{right.push(num);int rightTop=right.top();right.pop();left.push(rightTop);}}else if(left.size()==right.size()+1){if(num<=left.top()){left.push(num);int leftTop=left.top();left.pop();right.push(leftTop);}else {right.push(num);}}}double findMedian() {if(left.size()==right.size())return (left.top()+right.top())/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();*/