C++ STL堆相关函数的简单使用

C++ STL堆相关函数的简单使用

简单介绍下堆相关的函数的使用

堆不是容器，而是组织容器元素的一种特别方式。
只能确定堆的范围，即开始和结束迭代器指定的范围。
这意味着可以用容器中的元素子序列创建堆，可以在已生成的堆中添加元素。

以vector容器为例：
为了简化代码，vector的读取和输出被打包为两个函数 ↓

vector<int> get_input()
{
	int n;
	cin>>n;
	vector<int> nums; 
	for(int i=0; i<n; i++)
	{
		int x;
		cin>>x;
		nums.insert(nums.end(), x);
	}
	return nums;
}
void out(vector<int> nums)
{
	for(int i=0; i<nums.size(); i++)
	{
		cout<<nums[i]<<" ";
	}
	cout<<endl;
}

1.创建堆

/*
function : 将指定地址段的序列容器中的数据根据比较规则组织成堆
param 1  : 序列式容器的起始地址 
param 2  : 序列式容器的结束地址 
param 3  : 比较函数，默认使用less<>，即创建大顶堆
return   : ---
*/
make_heap(param1, param2, param3);

主函数：使用greater<int>创建一个小顶堆

make_heap(nums.begin(), nums.end(), greater<int>());

结果：

2.向堆中添加元素

注意：

1. 插入时的比较规则（即param3，比较函数）必须和创建堆时的相同，或者说一个堆能且只能用同一种比较规则
2. 新元素应该是最后一个元素，因此只需要调用相应容器的push_back，再调用push_heap即可将新元素插入推中

/*
function : 将指定地址段的序列容器中[最后一个]数据插入前面的堆中
param 1  : 序列式容器的起始地址 
param 2  : 序列式容器的结束地址 
param 3  : 比较函数，默认使用less<>，即插入大顶堆
return   : ---
*/
push_heap(param1, param2, param3);

主函数：向已经组织好的堆中插入一个新元素

make_heap(nums.begin(), nums.end(), greater<int>());
nums.push_back(6);
push_heap(nums.begin(), nums.end(), greater<int>());

结果：

3.删除堆顶元素

注意

1. 因为移除堆顶元素后，有一个调整的动作，那就要求比较规则（即param3，比较函数）必须和创建堆时的相同，或者说一个堆能且只能用同一种比较规则
2. pop_heap只是将元素交换到最后，没有移出容器，最后需要调用容器的pop_back，才将最后的元素移除

/*
function : 将指定地址段的序列容器中[第一个]数据放到最后，然后将前面的数据重新组织成堆
param 1  : 序列式容器的起始地址
param 2  : 序列式容器的结束地址 
param 3  : 比较函数，默认使用less<>，大顶堆删除与调整
return   : ---
*/
pop_heap(param1, param2, param3);

主函数：移除堆顶元素

make_heap(nums.begin(), nums.end(), greater<int>());
nums.push_back(6);
push_heap(nums.begin(), nums.end(), greater<int>());
pop_heap(nums.begin(), nums.end(), greater<int>());
nums.pop_back();

结果：

4.判断序列是否为一个堆

注意：
函数被调用时，要求比较规则（即param3，比较函数）必须和创建堆时的相同，或者说一个堆能且只能用同一种比较规则

/*
function : 判断序列容器是否满足堆的性质
param 1  : 序列式容器的起始地址 
param 2  : 序列式容器的结束地址
param 3  : 比较函数，默认使用less<>，判断是否满足大顶堆
return   :  true or false
*/
is_heap(param1, param2, param3);

5.堆排序

通过不断地把堆顶元素交换到序列的末尾，再调整前面的堆，因为堆顶元素具有极性（极大或极小），最终得到的序列是一个排序完的序列

• 如果是大顶堆，那么排序之后是升序
• 如果是小顶堆，那么排序之后是降序

/*
function : 将指定地址段的序列容器进行堆排序
param 1  : 序列式容器的起始地址
param 2  : 序列式容器的结束地址 
param 3  : 比较函数，默认使用less<>，大顶堆排序完之后，为升序
return   : ---
*/
sort_heap(param1, param2, param3);

主函数：堆排序

make_heap(nums.begin(), nums.end(), greater<int>());
sort_heap(nums.begin(), nums.end(), greater<int>());

结果：创建的小顶堆，排序后为降序

完整代码

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

vector<int> get_input()
{
	int n;
	cin>>n;
	vector<int> nums; 
	for(int i=0; i<n; i++)
	{
		int x;
		cin>>x;
		nums.insert(nums.end(), x);
	}
	return nums;
}

void out(vector<int> nums)
{
	for(int i=0; i<nums.size(); i++)
	{
		cout<<nums[i]<<" ";
	}
	cout<<endl;
}

int main()
{
	vector<int> nums = get_input();		
	/*
	填入上文[主函数]部分的代码 
	*/
	out(nums);

	return 0;
}