admin管理员组文章数量:1623789
C++ | STL | 大顶堆 | 小顶堆 | std::priority_queue
目录
C++ | STL | 大顶堆 | 小顶堆 | std::priority_queue
1.C++ greater()和less()[1]
1.1.greater()和less()定义
1.2.greater()和less()使用方法
2.大顶堆 | 小顶堆 | std::priority_queue[2]
2.1 std::priority_queue简述
2.2 priority_queue模板参数
2.3 成员函数
2.4 大顶堆与小顶堆
1.C++ greater()和less()[1]
1.1.greater()和less()定义
greater()和less()函数在头文件<functional>中,为C++STL中定义的函数包装器,具体功能为相应的算法提供比较接口,具体定义如下:
template <class T> struct greater {
bool operator() (const T& x, const T& y) const {return x>y;}
typedef T first_argument_type;
typedef T second_argument_type;
typedef bool result_type;
};
template <class T> struct less {
bool operator() (const T& x, const T& y) const {return x<y;}
typedef T first_argument_type;
typedef T second_argument_type;
typedef bool result_type;
};
1.2.greater()和less()使用方法
以sort()函数为例:
#include<iostream>
#include<vector>
#include<iterator>
#include<functional>
#include<algorithm>
using namespace std;
int main()
{
int A[]={1,4,3,7,10};
const int N=sizeof(A)/sizeof(int);
vector<int> vec(A,A+N);
ostream_iterator<int> output(cout," ");
cout<<"Vector vec contains:";
copy(vec.begin(),vec.end(),output);
cout<<"\nAfter greater<int>():";
sort(vec.begin(),vec.end(),greater<int>());//内置类型从大到小
copy(vec.begin(),vec.end(),output);
cout<<"\nAfter less<int>():";
sort(vec.begin(),vec.end(),less<int>()); //内置类型小大到大
copy(vec.begin(),vec.end(),output);
return 0;
}
输出结果:
2.大顶堆 | 小顶堆 | std::priority_queue[2]
2.1 std::priority_queue简述
对于这个模板类priority_queue,它是STL所提供的一个非常有效的容器。作为队列的一个延伸,优先队列包含在头文件 <queue>
中。
优先队列时一种比较重要的数据结构,它是有二项队列编写而成的,可以以O(log n) 的效率查找一个队列中的最大值或者最小值(堆结构),其中是最大值还是最小值是根据创建的优先队列的性质来决定的。
2.2 priority_queue模板参数
优先队列有三个参数,其声明形式为:
priority_queue< type, container, function>;
这三个参数,后面两个可以省略,第一个不可以。其中:
- type:数据类型;
- container:实现优先队列的底层容器,必须是可随机访问的容器,例如vector、deque,而不能使用list;
- function:元素之间的比较方式;
在STL中,默认情况下(不加后面两个参数)是以vector为容器,以 operator< 为比较方式,所以在只使用第一个参数时,优先队列默认是一个最大堆,每次输出的堆顶元素是此时堆中的最大元素。
2.3 成员函数
假设type类型为int,则:
- bool empty() const :返回值为true,说明队列为空;
- int size() const :返回优先队列中元素的数量;
- void pop() :删除队列顶部的元素,也即根节点
- int top() :返回队列中的顶部元素,但不删除该元素;
- void push(int arg):将元素arg插入到队列之中;
2.4 大顶堆与小顶堆
大顶堆
//构造一个空的优先队列(此优先队列默认为大顶堆)
priority_queue<int> big_heap;
//另一种构建大顶堆的方法
priority_queue<int,vector<int>,less<int> > big_heap2;
小顶堆
//构造一个空的优先队列,此优先队列是一个小顶堆
priority_queue<int,vector<int>,greater<int> > small_heap;
本文标签: 大顶堆stl小顶堆priorityqueuestd
版权声明:本文标题:C++ | STL | 大顶堆 | 小顶堆 | std::priority_queue 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/dianzi/1728896976a1178536.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论