首页 » C语言 » c++的STL中堆的运用

c++的STL中堆的运用

原文 http://blog.csdn.net/breeze_blows/article/details/79181325

2018-01-28 02:00:32阅读(493)

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

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


//堆的基本操作举例

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main () {
  int a[] = {1,2,3,5,6};
  vector<int> 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; i<v.size(); i++) 
  		cout << " " << v[i];
  return 0;
}
//利用堆的基本操作返回给出序列的最小的K个数字
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <set>
using namespace std;
   
vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int> v;
        
        make_heap(input.begin(), input.end(), greater<int>());
        for(int i = 1; i <= k; ++i)
        {
            v.push_back(input.front());
            pop_heap(input.begin(), input.end(), greater<int>());
            input.pop_back();
        }
        
        return v;
    } 
int main()
{
	vector<int> v;
	
	int n, m;
	cin >> n;
	for(int i = 0; i < n; ++i)
	{
		cin >> m;
		v.push_back(m);
	}
	
	vector<int> q = GetLeastNumbers_Solution(v, 2);
	
	for(int i = 0; i < q.size(); ++i)
	{
		cout << q[i];
	}
	
	return 0;
} 


最新发布

CentOS专题

关于本站

5ibc.net旗下博客站精品博文小部分原创、大部分从互联网收集整理。尊重作者版权、传播精品博文,让更多编程爱好者知晓!

小提示

按 Ctrl+D 键,
把本文加入收藏夹