找出m个数中最小的n个数的算法

　2009-10-29 11:59:01　来源：WEB开发网　闂傚倸鍊搁崐鎼佸磹妞嬪孩顐芥慨姗嗗厳缂傛氨鎲稿鍫罕闂備礁婀遍搹搴ㄥ窗閺嶎偆涓嶆い鏍仦閻撱儵鏌ｉ弴鐐测偓鍦偓姘炬嫹

闂傚倸鍊搁崐鎼佸磹妞嬪海鐭嗗〒姘ｅ亾妤犵偛顦甸弫鎾绘偐閹绘帞鈧參姊哄Ч鍥х仼闁诲繑鑹鹃悾鐑藉蓟閵夛妇鍘甸梺瑙勵問閸犳牠銆傛總鍛婄厱閹艰揪绱曟牎闂侀潧娲ょ€氫即鐛幒妤€绠ｆ繝闈涘暙娴滈箖鏌ｉ姀鈶跺湱澹曟繝姘厵闁绘劦鍓氶悘杈ㄤ繆閹绘帞澧涚紒缁樼洴瀹曞崬螖閸愬啠鍓濈换娑樼暆婵犱胶鏁栫紓浣介哺閹瑰洤鐣烽幒鎴僵闁瑰吀鐒﹂悗鎼佹⒒娴ｇ儤鍤€闁搞倖鐗犻獮蹇涙晸閿燂拷

濠电姷鏁告慨鐑藉极閸涘﹥鍙忔い鎾卞灩缁狀垶鏌涢幇闈涙灈鐎瑰憡绻冮妵鍕箻鐎靛摜鐣奸梺纭咁潐濞茬喎顫忕紒妯肩懝闁逞屽墮宀ｈ儻顦查悡銈夋煏閸繃鍋繛宸簻鎯熼梺瀹犳〃閼冲爼宕濋敃鈧—鍐Χ閸℃鐟愰梺鐓庡暱閻栧ジ宕烘繝鍥у嵆闁靛骏绱曢崢顏堟⒑閹肩偛鍔楅柡鍛⊕缁傛帟顦寸紒杈ㄥ笚濞煎繘鍩℃担閿嬵潟闂備浇妗ㄩ悞锕傚箲閸ヮ剙鏋侀柟鍓х帛閺呮悂鏌ㄩ悤鍌涘闂傚倸鍊搁崐鎼佸磹妞嬪孩顐芥慨姗嗗厳缂傛氨鎲稿鍫罕闂備礁婀遍搹搴ㄥ窗閺嶎偆涓嶆い鏍仦閻撱儵鏌ｉ弴鐐测偓鍦偓姘炬嫹　　闂傚倸鍊搁崐鎼佸磹閻戣姤鍤勯柤鍝ユ暩娴犳氨绱撻崒娆掑厡缂侇噮鍨堕妴鍐川閺夋垹鍘洪悗骞垮劚椤︻垶宕￠幎鑺ョ厪闊洦娲栨牎闂佽瀵掗崜鐔奉潖閾忓湱纾兼俊顖氭惈椤矂姊洪崷顓涙嫛闁稿妫濋幆鈧い蹇撴祩濡嫰姊洪崫鍕拱婵炲弶岣块幑銏犫攽婵犲嫮鏉搁梺鍝勬川婵兘鎮伴妷鈺傗拻濞达絽鎼敮璺侯熆閻熷府鏀荤紒鍌氱Т楗即宕煎锝呬壕闁哄啫鐗嗙粈鍐┿亜韫囧海顦﹀ù婊堢畺閺屻劌鈹戦崱娑扁偓妤€顭胯閸犳牠婀侀梺缁樕戦悷銉р偓姘煎枤缁粯銈ｉ崘鈺冨幈濡炪倖鍔戦崐鏇㈠几鎼淬劍鐓熼煫鍥ь儏閸旀粓鏌曢崶褍顏€殿喗娼欒灒闁告繂瀚濠碉紕鍋戦崐鎴﹀垂濞差亝鍋￠柍鍝勬噹缁犳牠鏌嶉埡浣告殲闁稿海鍠栭弻鏇㈠炊瑜嶇花濠氭煙閸戙倖瀚�

核心提示：/ created: 2007/3/18 filename: main.cpp author: Lichuang purpose: 测试模拟堆算法*/#include <algorithm>#include <iostream>#include <time.h>using name

/******************************************************************** 　　　 created:　　　 2007/3/18 　　　 filename:　　　　 main.cpp 　　　 author:　　　　　　　 Lichuang 　　　　　　 purpose:　　　测试模拟堆算法 *********************************************************************/ #include <algorithm> #include <iostream> #include <time.h> using namespace std; // push_heap为向堆中添加一个新的元素, 调用这个算法的前提是[First, Last)之间的元素满足堆的条件 // 新加入的元素为Last void　　　 push_heap(int* pFirst, int* pLast); // pop_heap为从堆中删除一个元素, 调用这个算法的前提是[First, Last)之间的元素满足堆的条件 // 被删除的元素被放置到Last - 1位置,由于这里是max-heap,所以被删除的元素是这个序列中最大的元素 void　　　 pop_heap(int* pFirst, int* pLast); // make_heap将序列[First, Last)中的元素按照堆的性质进行重组 void　　　 make_heap(int* pFirst, int* pLast); // 对堆进行排序, 调用这个函数可以成功排序的前提是[pFirst, pLast)中的元素符合堆的性质 void　　　 sort_heap(int* pFirst, int* pLast); // 判断一个序列[First, Last)是否满足堆的条件,是就返回1,否则返回0 char　　　 is_heap(int* pFirst, int* pLast); // 用于根据堆的性质调整堆, 将nValue放到位置nHoleIndex, 并且保证堆性质的成立 void　　　 adjust_heap(int *pFirst, int nHoleIndex, int nLen, int nValue); // 得到一个数组中最小的n个元素 void　　　 get_n_min(int *pArray, int nLen, int n); void　　　 display_array(int *pArray, int nLength); int main() { 　　　 srand(time(NULL)); 　　　 int Array[10]; 　　　 for(int i = 0; i < 10; ++i) 　　　　　　　 Array[i] = rand(); 　　　 get_n_min(Array, 10, 2); 　　　 return 0; } void get_n_min(int *pArray, int nLen, int n) { 　　　 int *pTmp = (int*)malloc(sizeof(int) * n); 　　　 if (NULL == pTmp) 　　　 { 　　　　　　　 perror("malloc error"); 　　　　　　　 return; 　　　 } 　　　 int i; 　　　 for (i = 0; i < n; ++i) 　　　　　　　 pTmp[i] = pArray[i]; 　　　 make_heap(pTmp, pTmp + n); 　　　 display_array(pTmp, n); 　　　 for (; i < nLen; ++i) 　　　 { 　　　　　　　 if (pArray[i] < pTmp[0]) 　　　　　　　　　　　　 adjust_heap(pTmp, 0, n, pArray[i]); 　　　 } 　　　 // 最后对堆进行排序　　　 sort_heap(pTmp, pTmp + n); 　　　 cout << "the min n elements of the array is:n"; 　　　 // 打印堆中的数据　　　 display_array(pTmp, n); 　　　 free(pTmp); } // push_heap为向堆中添加一个新的元素, 调用这个算法的前提是[First, Last)之间的元素满足堆的条件 // 新加入的元素为Last void push_heap(int* pFirst, int* pLast) { 　　　 int nTopIndex, nHoleIndex, nParentIndex; 　　　 int nValue; 　　　 nTopIndex = 0; 　　　 nHoleIndex = (int)(pLast - pFirst - 1); 　　　 nParentIndex = (nHoleIndex - 1) / 2; 　　　 nValue = *(pLast - 1); 　　　 // 如果需要插入的节点值比父节点大, 上溯继续查找　　　 while (nHoleIndex > nTopIndex && pFirst[nParentIndex] < nValue) 　　　 { 　　　　　　　 pFirst[nHoleIndex] = pFirst[nParentIndex]; 　　　　　　　 nHoleIndex = nParentIndex; 　　　　　　　 nParentIndex = (nHoleIndex - 1) / 2; 　　　 } 　　　 pFirst[nHoleIndex] = nValue; } // pop_heap为从堆中删除一个元素, 调用这个算法的前提是[First, Last)之间的元素满足堆的条件 // 被删除的元素被放置到Last - 1位置,由于这里是max-heap,所以被删除的元素是这个序列中最大的元素 void pop_heap(int* pFirst, int* pLast) { 　　　 int nValue; 　　　 nValue = *(pLast - 1); 　　　 *(pLast - 1) = *pFirst; 　　　 adjust_heap(pFirst, 0, (int)(pLast - pFirst - 1), nValue); } // make_heap将序列[First, Last)中的元素按照堆的性质进行重组 void make_heap(int* pFirst, int* pLast) { 　　　 int nLen, nParentIndex; 　　　 nLen = (int)(pLast - pFirst); 　　　 nParentIndex = (nLen - 1) / 2; 　　　 while (true) 　　　 { 　　　　　　　 // 对父节点进行调整, 把父节点的值调整到合适的位置　　　　　　　 adjust_heap(pFirst, nParentIndex, nLen, pFirst[nParentIndex]); 　　　　　　　 if (0 == nParentIndex) 　　　　　　　　　　　 return; 　　　　　　　 nParentIndex--; 　　　 } } // 对堆进行排序, 调用这个函数可以成功排序的前提是[pFirst, pLast)中的元素符合堆的性质 void sort_heap(int* pFirst, int* pLast) { 　　　 // 调用pop_heap函数, 不断的把当前序列中最大的元素放在序列的最后　　　 while(pLast - pFirst > 1) 　　　　　　　 pop_heap(pFirst, pLast--); } // 判断一个序列[First, Last)是否满足堆的条件,是就返回1,否则返回0 char is_heap(int* pFirst, int* pLast) { 　　　 int nLen, nParentIndex, nChildIndex; 　　　 nLen = (int)(pLast - pFirst); 　　　 nParentIndex = 0; 　　　 for (nChildIndex = 1; nChildIndex < nLen; ++nChildIndex) 　　　 { 　　　　　　　 if (pFirst[nParentIndex] < pFirst[nChildIndex]) 　　　　　　　　　　　 return 0; 　　　　　　　 // 当nChildIndex是偶数时, 那么父节点已经和它的两个子节点进行过比较了　　　　　　　 // 将父节点递增1 　　　　　　　 if ((nChildIndex & 1) == 0) 　　　　　　　　　　　 ++nParentIndex; 　　　 } 　　　 return 1; } // 一个静态函数仅供adjust_heap调用以证实JJHOU的结论 static void push_heap(int *pFirst, int nHoleIndex, int nTopIndex, int nValue) { 　　　 int nParentIndex; 　　　 nParentIndex = (nHoleIndex - 1) / 2; 　　　 while (nHoleIndex > nTopIndex && pFirst[nParentIndex] < nValue) 　　　 { 　　　　　　　 pFirst[nHoleIndex] = pFirst[nParentIndex]; 　　　　　　　 nHoleIndex = nParentIndex; 　　　　　　　 nParentIndex = (nHoleIndex - 1) / 2; 　　　 } 　　　 pFirst[nHoleIndex] = nValue; } // 对堆进行调整, 其中nHoleIndex是目前堆中有空洞的节点索引, nLen是待调整的序列长度 // nValue是需要安插进入堆中的值 void adjust_heap(int *pFirst, int nHoleIndex, int nLen, int nValue) { 　　　 int nTopIndex, nSecondChildIndex; 　　　 nTopIndex = nHoleIndex; 　　　 nSecondChildIndex = 2 * nTopIndex + 2; 　　　 while (nSecondChildIndex < nLen) 　　　 { 　　　　　　　 if (pFirst[nSecondChildIndex] < pFirst[nSecondChildIndex - 1]) 　　　　　　　　　　　 --nSecondChildIndex; 　　　　　　　 pFirst[nHoleIndex] = pFirst[nSecondChildIndex]; 　　　　　　　 nHoleIndex = nSecondChildIndex; 　　　　　　　 nSecondChildIndex = 2 * nHoleIndex + 2; 　　　 } 　　　 if (nSecondChildIndex == nLen) 　　　 { 　　　　　　　 pFirst[nHoleIndex] = pFirst[nSecondChildIndex - 1]; 　　　　　　　 nHoleIndex = nSecondChildIndex - 1; 　　　 } 　　　 // 以下两个操作在这个函数中的作用相同, 证实了<<STL源码剖析>>中P178中JJHOU所言　　　 //pFirst[nHoleIndex] = nValue; 　　　 push_heap(pFirst, nHoleIndex, nTopIndex, nValue); } void　　　 display_array(int *pArray, int nLength) { 　　　 for (int i = 0; i < nLength; ++i) 　　　　　　　 std::cout << pArray[i] << " "; 　　　 std::cout << std::endl; }