維護k個元素的最大堆，即用容量為k的最大堆存儲最小的k個數，k1設為大頂堆中最大元素。遍歷一次數列，n，每次遍歷一個元素x，與堆頂元素比 較，x<kmax，更新堆，否則不更新堆。

?

1 // 海量數據中，尋找最小的k個數（堆）.cpp : 定義控制臺應用程序的入口點。 2 3 #include "stdafx.h" 4 #include <string.h> 5 #define MAX 1000 6 7 void swap(int &a,int &b) 8 { 9 int c; 10 c=a; 11 a=b; 12 b=c; 13 } 14 15 void max_heapity(int heap[],int i,int len)//保持最大堆性質 16 { 17 int left=2*i, right=2*i+1,largest=-1; 18 if((left<=len)&&(heap[left]>heap[i])) 19 largest=left; 20 else 21 largest=i; 22 if((right<=len)&&(heap[right]>heap[largest])) 23 largest=right; 24 if(largest!=i) 25 { 26 swap(heap[largest],heap[i]); 27 max_heapity(heap,largest,len); 28 } 29 } 30 31 void build_maxheap(int heap[],int len) //建立最大堆 32 { 33 int index=len/2; 34 for(int i=index;i>=1;i--) 35 max_heapity(heap,i,len); 36 } 37 38 void main() 39 { 40 int k=5,heap[]={0,3,12,6,7,15,13,24,1,4,9,10,16,20,63,45,37,86};//這里只列了少量數據進行驗證，實際中應該從文件中讀取數據 41 //第一個元素不計入，因這里有關堆的算法都是從下標為1開始的 42 int len=sizeof(heap)/sizeof(heap[0]); 43 build_maxheap(heap,k);//建立k個元素的最大堆 44 for(int i=1;i<len;i++) 45 { 46 if(heap[i]<heap[1]) //如果遇到比堆頂元素小的元素，就更新堆 47 { 48 heap[1]=heap[i]; 49 max_heapity(heap,1,k); 50 } 51 } 52 for(int j=1;j<=k;j++) 53 printf("%4d",heap[j]); 54 }

?

轉載于:https://www.cnblogs.com/xingele0917/archive/2012/10/14/2723432.html

總結

以上是生活随笔為你收集整理的海量数据中，寻找最小的k个数。的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。