堆（heap）的STL操作

说明：

首先，

#include<vector>

vector，一个可以用于存放任意类型的动态数组的容器。

声明：vector<参数>参数名

例如，在对heap的操作中我们用到的是int型：vector<int> t;

基本操作：

                t.push_back(num)    加入数据num

                t.pop_back()            删除最后一个数据

                t.begin()                   队首

                t.end()                      队末（最后两个操作不是很懂，好像不能用来运算）

现在我们来创建一个动态数组：

for  (i = 1;i <= n;i++)
{
    int num;
    cin>>num;
    t.push_back(num);
}//创建了一个大小为n的动态数组

#include<algorithm> 

基本操作：

                make_heap(t.begin(),t.back(),cmp)    创建堆

bool cmp(int x,int y) { return x > y; }//小根堆，没有错，就是大于号

                pusu_heap(t,begin(),t.end(),cmp)    在增加元素后维护堆

                pop_heap(a.begin(),a.end(),cmp)    将第一个元素放到最后，并忽略它维护堆。与t.pop_back()一起使用可以删除堆的第一个元素

实例：

这个题目中取出最小元素后还需要将该元素进行一定运算再插入原来的数组，然后再取出插入过后的数组中最小的元素，反复进行该操作。如果每次都进行一次排序时间复杂度显然有点高，这种时候就特别适合用堆进行操作。

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
bool cmp(int a,int b)
{
	return a > b;
}
int main()
{
	int n,a,b,k,sum = 0,num,temp;
	cin>>n>>a>>b>>k;
	vector<int> t;
	int i,j;
	for  (i = 0;i < n;i++)
	{
		cin>>num;
		t.push_back(num);
	}
	make_heap(t.begin(),t.end(),cmp);
	for  (j = 1;j <= k;j++)
	{
		sum += t[0];
		pop_heap(t.begin(),t.end(),cmp);
		t[n - 1] = t[n - 1] * a + b;
		push_heap(t.begin(),t.end(),cmp);
	}
	cout<<sum;

	return 0;
}