来源:http://www.cnblogs.com/pugang/archive/2012/07/04/2576505.html
应用C++ STL以最小堆方法解决Top K 问题
问题的来源我想不必多言了,很多的面试题中,以及<编程之美>中都有对问题的描述,以及相关的解法,写本文的目的是以C++ STL的方式用最小堆解法解决这个问题。
那么什么是最小堆呢?
其实最小堆是一颗特殊二叉树,其父节点的key小于其孩子节点,对!最小堆不是堆,是二叉树!
最小堆解法其实可以将问题的时间复杂度缩减到nlgK, 但是本文由于没有在C++ STL 中找到合适的函数保持最小堆(如果用自己写代码可以做到lgk),所以必须每次重建最小堆(如果您有更好的建议,欢迎指点),因此,时间复杂度为nk, 另外本文假设k<<n.
#include <iostream> #include <algorithm> #include <vector> #include <functional> using namespace std; void TopKAlgorithm(int inputArray[], int nInputLength, int nOutputLength ){ //construct the minimum heap the size is K vector<int> vec(inputArray,inputArray+nOutputLength); make_heap (vec.begin(),vec.end(), greater<int>()); for(int i=nOutputLength; i<10; i++){ if(inputArray[i] >= vec[0]){ vec[0] = inputArray[i]; //此处其实只需要保持堆的性质即可,并不需要重建堆 make_heap (vec.begin(),vec.end(), greater<int>()); } } for(int i=0; i<nOutputLength; i++) { inputArray[i]=vec[i]; } } int main () { int InputValues[] = {10,200,30,5,15,110,2,42,6,36}; TopKAlgorithm(InputValues, 10, 3); cout << "The top K Values are:"; for (unsigned i=0; i<3; i++) { cout << " " << InputValues[i]; } cout << endl; return 0; }
总结
本文以最小堆解法解决了TOP K 问题,完全采用C++的STL原生函数加以实现,其中没有手动加入任何操作最小堆的代码,另外,本文的一个遗憾是第二次建堆的时候其实不是完全的必要,因为我们只需要保持对的性质就可以,欢迎批评指正,希望对大家有所帮助。