C++ | STL | std::priority_queue | 大顶堆与小顶堆实现
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;
上一篇: 学习C++中priority_queue用法(大顶堆和小顶堆)
下一篇: PriorityQueue, Lambda, and Comparator: Prioritizing with Efficiency
推荐阅读
-
二、代码实现YUV420图像的水平拼接
-
如何实现neon优化的yuv420转rgb24汇编代码,iOS/Android可用的具体操作步骤
-
YUV420图像的剪裁与填充操作
-
将YUV420图像转换为BGR图像的方法使用OpenCvSharp实现
-
区别:YUV420P 与 YUVJ420 有何异同?
-
YUV422(YUYV)与YUV420的互转研究
-
【Android RTMP】Android Camera 视频数据采集预览 ( NV21 图像格式 | I420 图像格式 | NV21 与 I420 格式对比 | NV21 转 I420 算法 )
-
Opencv实现yuv420P格式的读取
-
两种方法将YUV420P文件转换为PNG图像格式的Python实现
-
旋转90/180/270度:RGB与YUV420的转换