C++STL之优先级队列详解

转x33g5p2x  于2021-12-13 转载在 C/C++  
字(8.7k)|赞(0)|评价(0)|浏览(354)

priority_queue

虽然他叫优先级队列，但是它不符合队列的特性：

priority_queue的使用

函数声明接口说明
priority_queue()/priority_queue(first,last)构造一个空的优先级队列
empty( )检测优先级队列是否为空，是返回true，否则返回false
top( )返回优先级队列中最大(最小元素)，即堆顶元素
push(x)在优先级队列中插入元素x
pop()删除优先级队列中最大(最小)元素，即堆顶元素
void test_priority_queue()
{
    priority_queue<int> pq;//默认是大堆 -- 大的优先级高
    
    priority_queue<int,vector<int>,greater<int>> pq;//如果想控制成一个小堆 -- 小的优先级高
    
    pq.push(1);
    pq.push(10);
    pq.push(12);
    pq.push(3);
    pq.push(5);
    
    cout<<pq.top()<<endl;
    while(!pq.empty())
    {
        cout<<pq.top()<<" ";
    	pq.pop(); 
    }
    cout<<endl;
}
int main()
{
    
    return 0;
}

pop/top：取优先级最高的，默认是大的优先级高

实际上优先级队列的底层实现是堆

如果想要小的优先级高：

priority_queue<int,vector<int>,greater<int>> pq

我们传三个参数进去，可以看到优先级队列模板有三个参数，一个是数据类型，一个是被适配的容器，一个是仿函数，仿函数在下面我们 会讲解，一般第二个参数传入的容器需要满足可以随机访问，例如vector和deque。

下面我们来做一个题：

priority_queue在OJ中的使用

数组中第k个最大元素

题目描述：

方法一：排序，然后返回第k个最大的元素

class Solution
{
public:
    int findKthLargest(vector<int>& nums,int k)
    {
        //sort(nums.begin(),nums.end());//默认升序
        //return nums[nums.size()-k];
        
        sort(nums.begin(),nums.end(),greater<int>());//指定降序
        return nums[nums.size()-k];
    }
};

方法二：利用优先队列

class Solution
{
public:
    int findKthLargest(vector<int>& nums,int k)
    {
        priority_queue<int> maxHeap(nums.begin(),nums.end());
        while(--k)
        {
            maxHeap.pop();
        }
        return maxHeap.top();
    }
};

怎么将时间复杂度和空间复杂度更优？

方法三：

class Solution
{
public:
    int findKthLargest(vector<int>& nums,int k)
    {
        //建立K个数的小堆
        priority_queue<int,vector<int>,greater<int>> kMinHeap;
        for(size_t i = 0;i< k;++i)
        {
            kMinHeap.push(nums[i]);
        }
        for(size_t j = k;j<nums.size();++j)
        {
            if(kMinHeap.top()<nums[j])
            {
                kMinHeap.pop();
                kMinHeap.push(nums[j]);
            }
        }
        return kMinHeap.top();
    }
};

priority_queue模拟实现

通过对priority_queue的底层结构就是堆，因此此处只需对堆进行通用的封装即可，也就是用vector存储堆的元素，在priority_queue里面实现堆的操作即可，我们首先模拟实现优先级队列先不要第三个仿函数参数：

namespace Z
{
    template<class T,class Container = vector<T>>
    class priority_queue
    {
    public:
   		priority_queue()
        {};
    private:
        Container _con;
    };
}

我们来看看优先级队列的接口：

push的模拟实现

void AdjustUp(int child)
{
    //默认大堆
    int parent = (child-1)/2;
    while(child > 0)
    {
        if(_con[parent]<_con[child])
        {
            swap(_con[parent],_con[child]);
            child = parent;
            parent = (child-1)/2;
        }
        else
        {
            break;
        }
    }
}
void push(const T& X)
{
    _con.push_back(x);//先将元素插进去
    AdjustUp(_con[_con.size()-1]);//向上调整一次
}

pop模拟实现

void AdjustDown(size_t parent)
{
    size_t child = parent*2+1;
    while(child<_con.size())
    {
        if(child+1<_con.size() && _con[child]<_con[child+1])//右孩子存在且左孩子小于右孩子
        {
            child++;//右孩子
        }
        if(_con[parent]<_con[child])
        {
            swap(_con[parent],_con[child]);
            parent = child;
            child = parent*2+1;
        }
        else
        {
            braek;
        }
    }
}
void pop()
{
    swap(_con[0],_con[_con.size()-1])//先将第一个和最后一个元素互换
    _con.pop_back();//将最后一个元素pop掉
    AdjustDown(0);//向下调整一次
}

迭代器区间构造函数模拟实现

template<class InputIterator>
priority_queue(InputIterator first,InputIterator last)
{
    while(first!=last)
    {
		_con.push_back(*first);
        ++first;
    }
    //建堆
    for(size_t i = (_con.size()-1-1)/2;i >= 0;i--)
    {
        AjustDown(0);
    }
}

size的模拟实现

size_t size()
{
    return _con.size();
}

empty的模拟实现

bool empty()
{
    return _con.empty();
}

top的模拟实现

const T& top()
{
    return _con[0];
}

swap的模拟实现

void swap(priority_queue& x)
{
    swap(_con,x._con);
}

仿函数

对于上面的模拟实现我们还差点意思，因为库里面的优先级队列模板还有第三个参数：仿函数，我们前面学习优先级队列的使用的时候知道了我们实例化对象传参时多加一个仿函数参数就可以将优先级改变，接下来就说一说什么是仿函数：

前面我们知道加入了仿函数参数将默认建大堆改为了建小堆，而建大堆和建小堆的代码唯一的区别就在于向上调整算法和向下调整算法当中的比较符号的改变，那么我们怎么可以让它可以灵活改变呢？有人想到函数传参，但是我们仔细想想函数传参是不能传符号的，于是C++当中增加了仿函数/函数对象这个用法，通过仿函数类型的对象，我们可以像函数一样去使用。

仿函数是什么呢？仿函数是一个自定义类型：

template<class T>
class Less
{
public:
    bool operator()(T x,T y)
    {
        return x < y;
    }
};

我们来看一个例子：

class Less
{
public:
	bool operator()(int x,int y)
    {
        return x < y;
    }
};
int main()
{
    Less less;
    cout<<less(1,2)<<endl;
    //实际上是这样调用less.operator()(1,2)
    return 0;
}

当然我们还可以写Greater类来比较大于：

template<class T>
class Greater
{
public:
    bool operator()(T x,T y)
   	{
        return x > y;
    }
};

我们也可以看一个例子：

template<class T>
class Greater
{
public:
	bool operator()(T x,T y)
    {
        return x > y;
    }
};
int main()
{
    Greater<int> greater;
    cout<<greater(1,2)<<endl;
    //实际上是这样调用greater.operator()(1,2)
    return 0;
}

通过仿函数我们知道了：函数传参不可以传符号，但是可以传对象，传对象完成想要的功能

int main()
{
    priority_queue<int,vector<int>,Greater<int>> pq;
}

通过仿函数的讲解，我们就可以将向上调整算法和向下调整算法改一下：

//向上调整算法
void AdjustUp(int child)
{
    Compare com;
    int parent = (child - 1) / 2;
    while (child > 0)
    {
        if (com(_con[parent], _con[child]))
        {
            swap(_con[parent], _con[child]);
            child = parent;
            parent = (child - 1) / 2;
        }
        else
        {
            break;
        }
    }
}
//向下调整算法
void AdjustDown(size_t parent)
{
    Compare com;
    size_t child = parent * 2 + 1;
    while (child < _con.size())
    {
        if (child + 1 < _con.size() && com(_con[child], _con[child + 1]))
        {
            child = child + 1;
        }
        if (com(_con[parent], _con[child]))
        {
            swap(_con[parent], _con[child]);
            parent = child;
            child = parent * 2 + 1;
        }
        else
        {
            break;
        }
    }
}

typename

可能有的人疑问，在文档当中仿函数的显式实例化为什么是这么一长串呢？

这里面的value_type其实就是T：

而typename的作用是什么呢？

typename的第一个作用是用作模板里面，来声明某种类型：

template<typename T1, typename T2>

typename的第二个作用，首先我们来看这样一个例子：

template<class T>
void foo(const T& y)
{
	T::bar x;//编译到这里编译器不知道T类型是什么，还没有实例化出来，不知道去哪找bar
}

struct AA
{
	typedef int bar;
};

int main()
{
    AA aa;
    foo(aa);
}

这里会报错，为什么呢？

因为编译到T::bar x;这里，编译器不知道T类型是什么，还没有实例化出来，不知道去哪里找bar，此时我们需要将typename加上：

template<class T>
void foo(const T& y)
{
	typename T::bar x;//这样可以等调用这个函数实例化出来时才去找bar，这个时候加上typename就是为了告诉编译器，它后面的一大串字符串都是一个类型。
}
#include<vector>
#include<list>
#include<queue>
#include<iostream>
using namespace std;
#include<algorithm>
#include<functional>
namespace Z
{
    template<class T>
    class Less
    {
    public:
        bool operator()(T x, T y)
        {
            return x < y;
        }
    };

    template<class T>
    class Greater
    {
    public:
        bool operator()(T x, T y)
        {
            return x > y;
        }
    };
    template<class T, class Container = vector<T>, class Compare = Less<T>>
    //默认用Less仿函数，比较的是小于，建大堆,如果传Greater仿函数，比较的是大于，建小堆
    class priority_queue
    {
    public:
        priority_queue()
        {}
        template<class InputIterator>
        priority_queue(InputIterator first, InputIterator last)
        {
            //将数据插入进去
            while (first != last)
            {
                _con.push_back(*first);
                ++first;
            }
            //建堆
            for (int i = (_con.size() - 1 - 1) / 2; i >= 0; --i)
            {
                AdjustDown(0);
            }

        }
        //向上调整算法
        void AdjustUp(int child)
        {
            Compare com;
            int parent = (child - 1) / 2;
            while (child > 0)
            {
                //if(_con[parent] < _con[child])
                if (com(_con[parent], _con[child]))
                {
                    swap(_con[parent], _con[child]);
                    child = parent;
                    parent = (child - 1) / 2;
                }
                else
                {
                    break;
                }
            }
        }
        //向下调整算法
        void AdjustDown(size_t parent)
        {
            Compare com;
            size_t child = parent * 2 + 1;
            while (child < _con.size())
            {
                //if(child+1<_con.size() && _con[child]<_con[child+1])
                if (child + 1 < _con.size() && com(_con[child], _con[child + 1]))
                {
                    child = child + 1;
                }
                //if(_con[parent]<_con[child])
                if (com(_con[parent], _con[child]))
                {
                    swap(_con[parent], _con[child]);
                    parent = child;
                    child = parent * 2 + 1;
                }
                else
                {
                    break;
                }
            }
        }
        void push(const T& X)
        {
            _con.push_back(X);
            AdjustUp(_con.size() - 1);
        }
        void pop()
        {
            swap(_con[0], _con[_con.size() - 1]);
            _con.pop_back();
            AdjustDown(0);
        }
        const T& top()
        {
            return _con[0];
        }
        size_t size()
        {
            return _con.size();
        }
        bool empty()
        {
            return _con.empty();
        }
        private:
            Container _con;
    };
    
    void test_priority_queue()
    {
        //priority_queue<int> pq;//默认是大堆 -- 大的优先级高

        Z::priority_queue<int, vector<int>, greater<int>> pq;//如果想控制成一个小堆 -- 小的优先级高

        pq.push(1);
        pq.push(10);
        pq.push(12);
        pq.push(3);
        pq.push(5);

        cout << pq.top() << endl;
        while (!pq.empty())
        {
            cout << pq.top() << " ";
            pq.pop();
        }
        cout << endl;
    }
}

仿函数的变异玩法

注意：

如果在priority_queue中放自定义类型的数据，用户需要在自定义类型中提供> 或者< 的重载。

class Date
{
public:
    Date(int year =1900,int month = 1,int day = 1)
    : _year(year)
    , _month(month)
    , _day(day)
    {}
    //重载<
    bool operator<(const Date& d)const
    {
        return (_year < d._year) ||
        (_year == d._year && _month < d._month) ||
        (_year == d._year && _month == d._month && _day < d._day);
    }
	friend ostream& operator<<(ostream& _cout, const Date& d);
    friend class PDateLess;
}
//重载<<
ostream& operator<<(ostream& _cout, const Date& d)
{
    _cout << d._year << "-" << d._month << "-" << d._day;
    return _cout;
}

int main()
{
    priority_queue<Date> pq;//存日期类对象
    pq.push(Date(2021,11,24));
    pq.push(Date(2021,10,24));
    pq.push(Date(2021,12,24));
    pq.push(Date(2022,11,24));
    
    cout<<pq.top()<<endl;
    pq.pop();
    //选出最大
    return 0;
}

我们还可以这样玩：当传的时Date*时，用less仿函数会有问题：

int main()
{
    priority_queue<Date*> pq;//存日期类对象
    pq.push(new Date(2024,11,24));
    pq.push(new Date(2021,10,24));
    pq.push(new Date(2021,12,24));
    pq.push(new Date(2022,11,24));
    
    cout<<*pq.top()<<endl;
    pq.pop();
    //选出最大
    return 0;
}

为什么呢？因为我们的数据类型为指针，仿函数类型的重载函数比较的是地址大小，所以会出问题

这是一种仿函数的变异玩法，我们可以控制仿函数比较方式我们需要另外写个仿函数：

class PDateLess
{
public:
	bool operator()(const Date*p1,const Date* p2)
    {
        if(p1->_year< p2->_year
          ||(p1->_year==p2->_year&&p1->_month<p2->_month)
          ||(p1->_year==p2->_year&&p1->_month==p2->_month&&p1->_day<p2->_day)
         {
             return true;
         }
         else
         {
             return false;
         }
         //或者这样比较，前提是自定义类型中重载了<运算符
         //return *p1 < *p2;
    }
};
int main()
{
    priority_queue<Date*,vector<Date*>,PDateLess> pq;//存日期类对象
    pq.push(new Date(2024,11,24));
    pq.push(new Date(2021,10,24));
    pq.push(new Date(2021,12,24));
    pq.push(new Date(2022,11,24));
    
    cout<<pq.top()<<endl;
    pq.pop();
    //选出最大
    return 0;
}

版权说明 : 本文为转载文章, 版权归原作者所有 版权申明

原文链接 : https://blog.csdn.net/attemptendeavor/article/details/121914810

内容来源于网络，如有侵权，请联系作者删除！

c++容器开发语言优先级队列

相关文章

    查看更多
    微信公众号

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新文章

    更多
    • 蜀ICP备13028337号-1 大数据知识库 https://www.saoniuhuo.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com