达内网站开发视频教程,wordpress phpcms 开发,可以发布免费广告的平台,wordpress百家号插件一、堆的定义
二、堆#xff08;优先队列#xff09;
堆通常用于实现优先队列#xff08;priority_queue#xff09;#xff0c;大顶堆相当于元素按从大到小的顺序出队的优先队列。从使用角度来看#xff0c;我们可以将“优先队列”和“堆”看作等价的数据结构。
堆的…一、堆的定义
二、堆优先队列
堆通常用于实现优先队列priority_queue大顶堆相当于元素按从大到小的顺序出队的优先队列。从使用角度来看我们可以将“优先队列”和“堆”看作等价的数据结构。
堆的常见用法
/* 初始化堆 */
// 初始化小顶堆
priority_queueint, vectorint, greaterint minHeap;
// 初始化大顶堆
priority_queueint, vectorint, lessint maxHeap;/* 元素入堆 */
maxHeap.push(1);
maxHeap.push(3);
maxHeap.push(2);
maxHeap.push(5);
maxHeap.push(4);/* 获取堆顶元素 */
int peek maxHeap.top(); // 5/* 堆顶元素出堆 */
// 出堆元素会形成一个从大到小的序列
maxHeap.pop(); // 5
maxHeap.pop(); // 4
maxHeap.pop(); // 3
maxHeap.pop(); // 2
maxHeap.pop(); // 1/* 获取堆大小 */
int size maxHeap.size();/* 判断堆是否为空 */
bool isEmpty maxHeap.empty();/* 输入列表并建堆 */
vectorint input{1, 3, 2, 5, 4};
priority_queueint, vectorint, greaterint minHeap(input.begin(), input.end());
三、堆的常见应用
优先队列堆通常作为实现优先队列的首选数据结构其入队和出队操作的时间复杂度均为 0(logn) 而建队操作为 0(n)这些操作都非常高效。堆排序给定一组数据我们可以用它们建立一个堆然后不断地执行元素出堆操作从而得到有序数据。获取最大的 K 个元素这是一个经典的算法问题同时也是一种典型应用例如选择热度前 10 的新闻作为微博热搜选取销量前 10 的商品等。
四、具体思路top-k问题 初始化一个小顶堆其堆顶元素最小。先将数组的前 k 个元素依次入堆。从第 k1 个元素开始若当前元素大于堆顶元素则将堆顶元素出堆并将当前元素入堆。遍历完成后堆中保存的就是最大的 k个元素。 /* 基于堆查找数组中最大的 k 个元素 */
priority_queueint, vectorint, greaterint topKHeap(vectorint nums, int k) {// 初始化小顶堆priority_queueint, vectorint, greaterint heap;// 将数组的前 k 个元素入堆for (int i 0; i k; i) {heap.push(nums[i]);}// 从第 k1 个元素开始保持堆的长度为 kfor (int i k; i nums.size(); i) {// 若当前元素大于堆顶元素则将堆顶元素出堆、当前元素入堆if (nums[i] heap.top()) {heap.pop();heap.push(nums[i]);}}return heap;
}
总共执行了 n 轮入堆和出堆堆的最大长度为 k 因此时间复杂度为 0(nlogk)。该方法的效率很高当 k 较小时时间复杂度趋向0(n) 当k 较大时时间复杂度不会超过 0(nlogn) 。
另外该方法适用于动态数据流的使用场景。在不断加入数据时我们可以持续维护堆内的元素从而实现最大的 k个元素的动态更新
五、习题
215. 数组中的第K个最大元素
class Solution {
public:int findKthLargest(vectorint nums, int k) {//建大顶堆priority_queueint,vectorint,greaterintheap;int nnums.size();for(int i0;ik;i){heap.push(nums[i]);}for(int ik;in;i){if(nums[i]heap.top()){heap.pop();heap.push(nums[i]);} }return heap.top();}
};
264. 丑数 II
给你一个整数 n 请你找出并返回第 n 个 丑数 。
丑数 就是质因子只包含 2、3 和 5 的正整数。
思路如果x是丑数则2x、3x、5x也是丑数。所以我们不妨使用一个优先队列存储这些丑数。
每次取出堆顶元素 x则 x 是堆中最小的丑数由于 2x,3x,5x 也是丑数因此将 2x,3x,5x加入堆。
上述做法会导致堆中出现重复元素的情况。为了避免重复元素可以使用哈希集合去重避免相同元素多次加入堆。
哈希去重
unordered_setlong seen;//建立哈希表
//seen.count(x)//对x元素计数。if(!seen.count(x))//x此时一个都没有
seen.insert(x);//插入到哈希表中此时数量就为一了
class Solution {
public:int nthUglyNumber(int n) {//哈希表去重unordered_setlong seen;vectorintfactors{2,3,5};priority_queuelong,vectorlong,greaterlongheap;seen.insert(1L);heap.push(1L);int ugly0;for(int i0;in;i){long currheap.top();heap.pop();ugly(int)curr;for(int factor:factors){long nextcurr*factor;if(!seen.count(next)){seen.insert(next);heap.push(next);}}}return ugly;}
};
另外一个方法. - 力扣LeetCode
