寻找最大的K个数，Top K问题的堆实现
<div id="cnblogs_post_body">寻找最大的K个数，如果所有的数据全部可以放入内存，就可以使用random select算法在线性时间内寻找第K大的数，再得到最大的K个数。
参考：http://www.cnblogs.com/luxiaoxun/archive/2012/08/06/2624799.html
如果不能把所有数据的数据都一次性放入内存，就可以维护一个大小为K的堆，找最大的K个数，就维护一个小根堆，堆顶元素为这最大的K个数中的最小元素。具体实现参考下面两个例子：
2亿个整数中求最大的100万之和
题目：有一个文件中保存了2亿个整数，每个整数都以' '分隔。求最大的100万个整数之和。
算法：
1. 首先建立一个容量为100万（Top K）的int数组，从文件读取整数填充。
2. 利用堆维护该100万条记录（确保堆顶元素为最小值）
3. 从文件中读取一个整数与堆顶元素比较，如果大于堆顶元素则替换该元素，并调整堆的结构。
4. 重复步骤3一直到数据读取完
5. 将数组中的元素全部相加，得到结果
参考代码：
<div class="cnblogs_code" >http://images.cnblogs.com/OutliningIndicators/ContractedBlock.gifhttp://images.cnblogs.com/OutliningIndicators/ExpandedBlockStart.gifView Code <div id="cnblogs_code_open_44ba1fd0-0324-4945-82f0-7ede20ea5eaa" class="cnblogs_code_hide">#include <iostream> using namespace std; template<class T>class CTopK{public: CTopK(); ~CTopK(); T*m_Data; int GetTopK(const char* sFile, int& nTop);private: void Clear(); void HeapAdjust(int nStart, int nLen); void BuildHeap(int nLen);}; template<class T>CTopK<T>::CTopK(){ m_Data = NULL;} template<class T>CTopK<T>::~CTopK(){ Clear();} template<class T>void CTopK<T>::Clear(){ if (NULL != m_Data) { delete[] m_Data; m_Data = NULL; }} //获取前top的k个数 template<class T>int CTopK<T>::GetTopK(const char* sFile, int& nTop){ FILE* fp = NULL; T fData; int i = 0; //判断输入参数 if ( (NULL == sFile) || (nTop <= 0) ) { cout << "error parameter" << endl; return -1; } //清除操作 Clear(); //打开文件 fp = fopen(sFile, "r"); if (NULL == fp) { cout << "open file failed!" << endl; return -1; } //分配空间 m_Data = new T; if (NULL == m_Data) { cout << "new operator failed!" << endl; return -1; } cout << "please wait..." << endl; //读取前nTop个数据,注意数据的类型T for (i = 0; i < nTop; i++) { if (EOF != fscanf(fp, "%d", &fData)) { m_Data = fData; } else { break; } } //最大的个数小于nTop,求前i个数据 if (i < nTop) { nTop = i; } else { BuildHeap(nTop);//建立小顶堆 while (EOF != fscanf(fp, "%d", &fData)) { if (fData > m_Data[0]) { //交换并调整堆 m_Data[0] = fData; HeapAdjust(0, nTop); } } } return 0;} //调整小根堆，堆顶为Top K最小 template<class T>void CTopK<T>::HeapAdjust(int nStart, int nLen){ int nMinChild = 0; T fTemp; while ( ( 2 * nStart + 1) < nLen) { nMinChild = 2 * nStart + 1; if ( (2 * nStart + 2) < nLen) { //比较左子树和右子树,记录最小值的Index if (m_Data[2 * nStart + 2] < m_Data[2 * nStart + 1]) { nMinChild = 2 * nStart + 2; } } //change data if (m_Data > m_Data) { //交换nStart与nMaxChild的数据 fTemp = m_Data; m_Data = m_Data; m_Data = fTemp; //堆被破坏,需要重新调整 nStart = nMinChild; } else { //比较左右孩子均大则堆未破坏,不再需要调整 break; } }} //建立堆 template<class T>void CTopK<T>::BuildHeap(int nLen){ int i = 0; T nTemp; //将m_Data建成小根堆，这里只维护一个小根堆，不排序 for (i = nLen / 2- 1; i >= 0; i--) { HeapAdjust(i, nLen); }} int main(int argc, char* argv[]){ char szFile[100] = {0}; int nNum = 0; CTopK<int> objTopSum; cout << "please input count file name:" << endl; cin >> szFile; cout << "please input top num:"<< endl; cin >> nNum; objTopSum.GetTopK(szFile, nNum); int fSum = 0; for (int i = 0; i < nNum; i++) { cout<<objTopSum.m_Data<<" "; fSum += objTopSum.m_Data; } cout << "\ntop " << nNum << " value = " << fSum << endl; return 0;}
页:
[1]