想要得到N个数中最大的K个数,典型的思路就是设置一个数组arr[K],然后遍历N个数,判断当前数和数组arr[k]中最小的数,如果它大于数组中最小的数,则置换。在这个数组中寻找最小的数,如果无序的话,很明显复杂度即为O(K),如果排序的话,维护一个有序数列,并且每次都是取该序列最小值进行比较,就自然地想到了小根堆了。
下面是使用c++的stl中的堆算法实现的代码,由于stl只支持四种算法:
- [**push_heap**](http://www.cplusplus.com/reference/algorithm/push_heap/)
- Push element into heap range (function template)
- [**pop_heap**](http://www.cplusplus.com/reference/algorithm/pop_heap/)
- Pop element from heap range (function template)
- [**make_heap**](http://www.cplusplus.com/reference/algorithm/make_heap/)
- Make heap from range (function template )
- [**sort_heap**](http://www.cplusplus.com/reference/algorithm/sort_heap/)
- Sort elements of heap (function template)
但是,可以稍微变通一下,因为pop_heap的实现就是将第一个元素与最后一个元素互换,然后再对前k-1个元素使用max-heapify算法调整堆结构,所以,我们可以每次比较当前元素和堆的第一个元素,如果大于它,则将该元素插入当前数组最后一个位置,应用pop_heap维护,再弹出最后一个元素即可。
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> KMaxNumber(int *arr,int i, int j, int k){
vector<int> vec;
int t;
for(t = i; t < k + i; ++t){
vec.push_back(arr[t]);
push_heap(vec.begin(),vec.end() ,greater<int>());
}
/*for(; t <= j; ++t){这个更直观,但是要进行两次维护!
if(vec[0] < arr[t]){
pop_heap(vec.begin(), vec.end(), greater<int>());
vec[k-1] = arr[t];
push_heap(vec.begin(), vec.end(), greater<int>());
}
}*/
for(; t <= j; ++t){
if(vec[0] < arr[t]){
vec.push_back(arr[t]);
pop_heap(vec.begin(), vec.end(), greater<int>());
vec.pop_back();
}
}
sort_heap(vec.begin(), vec.end(),greater<int>());
return vec;
}
int main(){
int arr[100] = {3,4,11,6,40,5,6,7,8,9,1,2,3,25};
vector<int> vec = KMaxNumber(arr, 0, 13, 5);
for(vector<int>::iterator iter = vec.begin(); iter < vec.end(); ++iter)
cout << *iter << " ";
cout << endl;
return 1;
}
原文链接: https://www.cnblogs.com/xiaolongren2012/archive/2012/12/26/2833655.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/73639
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!