c++的STL中堆的运用

2018-01-29 12:40:05来源:网络收集作者:程序诗人人点击

分享

STL中的建立的队默认是最大堆,要想用最小堆的话,必须要在push_heap,pop_heap,make_heap等每一个函数后面加第三个参数greater(),括号不能省略


make_heap(_First, _Last, _Comp); //默认是建立最大堆的。对int类型,可以在第三个参数传入greater()得到最小堆。
push_heap (_First, _Last); //在堆中添加数据,要先在容器中加入数据,再调用push_heap ()
pop_heap(_First, _Last); //在堆中删除数据,要先调用pop_heap()再在容器中删除数据
sort_heap(_First, _Last); //堆排序,排序之后就不再是一个合法的heap了

//堆的基本操作举例#include
#include
#include
using namespace std;
int main () {
int a[] = {1,2,3,5,6};
vector v(a, a + sizeof(a)/sizeof(a[0]));
make_heap(v.begin(),v.end());
cout << "initial max of heap : " << v.front() << endl;
pop_heap(v.begin(),v.end()); v.pop_back();
cout << "max of heap after pop : " << v.front() << endl;
v.push_back(7); push_heap(v.begin(),v.end());
cout << "max of heap after push: " << v.front() << endl;
sort_heap (v.begin(),v.end());
cout << "sorted range :";
for (unsigned i=0; icout << " " << v[i];
return 0;
}//利用堆的基本操作返回给出序列的最小的K个数字#include
#include
#include
#include
#include
#include
using namespace std;vector GetLeastNumbers_Solution(vector input, int k) {
vector v; make_heap(input.begin(), input.end(), greater());
for(int i = 1; i <= k; ++i)
{
v.push_back(input.front());
pop_heap(input.begin(), input.end(), greater());
input.pop_back();
} return v;
}
int main()
{
vector v;int n, m;
cin >> n;
for(int i = 0; i < n; ++i)
{
cin >> m;
v.push_back(m);
}vector q = GetLeastNumbers_Solution(v, 2);for(int i = 0; i < q.size(); ++i)
{
cout << q[i];
}return 0;
}

最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台