首页 > 编程语言 >【算法】堆与优先级队列

【算法】堆与优先级队列

时间:2024-09-19 11:56:00浏览次数:14  
标签:优先级 队列 元素 int 算法 heap size

【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();
 */

标签:优先级,队列,元素,int,算法,heap,size
From: https://blog.csdn.net/waluolandao/article/details/142243279

相关文章

  • 多输入多输出 | Matlab实现DBO-BP蜣螂算法优化BP神经网络多输入多输出预测
    多输入多输出|Matlab实现DBO-BP蜣螂算法优化BP神经网络多输入多输出预测目录多输入多输出|Matlab实现DBO-BP蜣螂算法优化BP神经网络多输入多输出预测预测效果基本介绍程序设计往期精彩参考资料预测效果基本介绍多输入多输出|Matlab实现DBO-BP蜣螂算法优化BP神经网络多输入......
  • 一区霜冰算法+双向深度学习模型+注意力机制!RIME-BiTCN-BiGRU-Attention
    一区霜冰算法+双向深度学习模型+注意力机制!RIME-BiTCN-BiGRU-Attention目录一区霜冰算法+双向深度学习模型+注意力机制!RIME-BiTCN-BiGRU-Attention效果一览基本介绍程序设计参考资料效果一览基本介绍1.Matlab实现RIME-BiTCN-BiGRU-Attention霜冰算法优化双向时间卷积双向门控循环......
  • 顶刊算法 | Matlab实现鹈鹕算法POA-CNN-LSTM-Multihead-Attention多头注意力机制多变
    顶刊算法|Matlab实现鹈鹕算法POA-CNN-LSTM-Multihead-Attention多头注意力机制多变量时间序列预测,优化前后对比目录顶刊算法|Matlab实现鹈鹕算法POA-CNN-LSTM-Multihead-Attention多头注意力机制多变量时间序列预测,优化前后对比预测效果基本介绍程序设计参考资料预测效果基本......
  • CNN-SVM模型 | Matlab实现SO-CNN-SVM蛇群算法优化卷积神经网络结合支持向量机多特征分
    CNN-SVM模型|Matlab实现SO-CNN-SVM蛇群算法优化卷积神经网络结合支持向量机多特征分类预测目录CNN-SVM模型|Matlab实现SO-CNN-SVM蛇群算法优化卷积神经网络结合支持向量机多特征分类预测分类效果基本描述程序设计参考资料分类效果基本描述1.Matlab实现SO-CNN-SVM蛇群算法优化......
  • 【开题报告+背景+源码】基于过滤协同算法苗族银饰推荐系统的设计与实现
    项目背景与意义课题苗族银饰推荐系统,应用Java技术设计开发一个苗族银饰推荐系统,实现用户购买苗族银饰商品方便快捷,不受时间和空间的限制功能,提供用户能够更快更好地获取自己想要的苗族银饰商品推荐服务,达到向消费者提供商品推荐,帮助他们发现感兴趣的苗族银饰商品并增加购买意......
  • 基于档案演化路径的快速收敛EO多目标优化算法及其在工程设计问题中的应用
    目录1.摘要2.基于档案演化路径机制的快速收敛多目标平衡优化算法(FC‑MOEO/AEP)2.1单目标平衡优化算法EO2.2多目标平衡优化算法FC‑MOEO/AEP3.结果展示4.参考文献5.代码获取1.摘要在实际的工程优化问题中,耗时的目标函数是不可避免的。这类函数使得元启发式方法......
  • 算法:动态规划思路(仅作记录)
    以leetcode70题爬楼梯为例:假设你正在爬楼梯。需要n阶你才能到达楼顶。每次你可以爬1或2个台阶。你有多少种不同的方法可以爬到楼顶呢?递归一共两种爬楼梯的方式如果最后一步要用到方法1,那么我们得先爬到n−1,要解决的问题缩小成:从0爬到n−1有多少种不同的方法。......
  • Java-数据结构-优先级队列(堆)-(一) (;´д`)ゞ
    文本目录:❄️一、优先级队列:     ➷1、概念:❄️二、优先级队列的模拟实现:     ➷1、堆的概念:     ➷ 2、堆的性质:      ➷ 3、堆的创建: ▶向下调整:       ➷ 4、堆的插入和删除:    ▶堆的插入: ☞......
  • 自动驾驶运动规划学习_碰撞检测算法_GJK
    自动驾驶运动规划学习:碰撞检测算法:GJKGilbert–Johnson–Keerthi(GJK)算法,是一种用于检测两个凸集是否重叠的高效算法,并且可以得到两个凸集的最小距离.1.4.1 GJK算法原理1.4.1.1 闵可夫斯基差(Minkowski Difference)1.4.1.3 凸性在二维空间中,如果一个凸集包含原......
  • Dijkstra 算法
    普通堆实现的Dijkstra算法时间复杂度为O(m*logm),m为边数distance[i]表示从源点到i点的最短距离,visited[i]表示i节点是否从小根堆弹出过准备好小根堆,小根堆存放记录:(x点,源点到x的距离),小根堆根据距离排序令distance[源点]=0,(源点,0)入堆从小根堆弹出(u......