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;   

---