应用C++ STL以最小堆方法解决Top K 问题.pdf

应用C++STL以最小堆方法解决TopK问题

问题的来源我想不必多言了，很多的面试题中，以及编程之美中都

有对问题的描述，以及相关的解法，写本文的目的是以C++STL的

方式用最小堆解法解决这个问题。

那么什么是最小堆呢？

其实最小堆是一颗特殊二叉树，其父节点的key小于其孩子节点，对！

最小堆不是堆，是二叉树！

最小堆解法其实可以将问题的时间复杂度缩减到nlgK,但是本文由于

没有在C++STL中找到合适的函数保持最小堆(如果用自己写代码可

以做到lgk)，所以必须每次重建最小堆(如果您有更好的建议，欢迎

指点)，因此，时间复杂度为nk,另外本文假设kn.

#includeiostream

#includealgorithm

#includevector

#includefunctional

usingnamespacestd;

voidTopKAlgorithm(intinputArray[],intnInputLength,intnOu

tputLength)

{

//constructtheminimumheapthesizeisK

vectorintvec(inputArray,inputArray+nOutputLength);

make_heap(vec.begin(),vec.end(),greaterint());

for(inti=nOutputLength;i10;i++)

{

if(inputArray[i]=vec[0])

{

vec[0]=inputArray[i];

//此处其实只需要保持堆的性质即可，并不需要重

建堆

make_heap(vec.begin(),vec.end(),greaterint());

}

}

for(inti=0;inOutputLength;i++)

{

inputArray[i]=vec[i];

}

}

intmain()

{

intInputValues[]={10,200,30,5,15,110,2,42,6,36};

TopKAlgorithm(InputValues,10,3);

coutThetopKValuesare:;

for(unsignedi=0;i3;i++)

{

coutInputValues[i];

}

coutendl;

return0;

}

总结

本文以最小堆解法解决了TOPK问题，完全采用C++的STL原生函

数加以实现，其中没有手动加入任何操作最小堆的代码，另外，本文

的一个遗憾是第二次建堆的时候其实不是完全的必要，因为我们只需

要保持对的性质就可以，欢迎批评指正，希望对大家有所帮助。