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;