首页 > 代码库 > 求数组最大k个数的问题(堆的应用)
求数组最大k个数的问题(堆的应用)
1 无顺序的一个数组求最大的k个数
1)笨方法,先用快速排序对数组排序在找前k个;
2) 用堆,先建立k小顶堆,再扫描整个数组,堆顶为k个数中最小的数;
/************************************/ //寻找在数组中最大的K个数 //小顶堆插入 void constructHeap(int a[],int n,int value){ a[n] = value; int j,temp = value; j = (n-1)/2; while (j>=0 && n!=0) { if(a[j] <= temp) break; a[n] = a[j]; n = j; j = (n-1)/2; } a[n] = temp; } //堆更新 void UpdataHeap(int a[],int index,int n) { int j,temp = a[index]; j = 2*index + 1; while (j < n) { if(j+1 < n && a[j+1] < a[j]) ++j; if(a[j] >= temp) break; a[index] = a[j]; index = j; j = index*2 +1; } a[index] = temp; } void MaxK(int a[],int n,int k){ int i; int *temp = new int[k]; for (i=0;i<n;++i) { if(i < k) constructHeap(temp,i,a[i]);//先构造k堆 else { if (temp[0] < a[i]) { temp[0] = a[i]; UpdataHeap(temp,0,k);//更新k堆; } } } for (i=0;i<k;++i) { cout<<temp[i]<<" "; } delete []temp; }
2 求N个降序数组的K个最大的数
http://www.cnblogs.com/ywl925/p/3794852.html
1. 建立大顶堆,维度为数组的个数,这里为20(第一次 插入的是每个数组中最大的值,即第一个元素)。
2. 删除最大堆堆顶,保存到数组或者栈中,然后向最大堆插入删除的元素所在数组的下一个元素。
3. 重复第1,2个步骤,直到删除个数为最大的K个数,这里为500.
/************************************/ //N个降序数组,找到最大的K个数 //大顶堆 void constructHeap1(int a[],int n,int value){ a[n] = value; int j,temp = value; j = (n-1)/2; while (j>=0 && n!=0) { if(a[j] >= temp) break; a[n] = a[j]; n = j; j = (n-1)/2; } a[n] = temp; } //堆更新 void UpdataHeap1(int a[],int index,int n) { int j,temp = a[index]; j = 2*index + 1; while (j < n) { if(j+1 < n && a[j+1] > a[j]) ++j; if(a[j] <= temp) break; a[index] = a[j]; index = j; j = index*2 +1; } a[index] = temp; } void GetMaxK(){ const int rows = 20; const int cols = 500; const int K = 500; int data[rows][cols]; int result[K];//前500 int heap[20];//堆 int i,j; for (i=0;i<rows;++i) { for (j=0;j<cols;++j ) { data[i][j] = rand(); } } //快速排序 for (i = 0;i<rows;++i) { QuikSortDown(data[i],0,cols-1); } //开始 for(j=0;j<cols;++j) { for (i=0;i<rows;++i) { if(0 == j) constructHeap1(heap,i,data[i][0]);//创建堆 else{ if((j-1)*rows + i >K-1 ) break; result[(j-1)*rows + i] = heap[0]; heap[0] = data[i][j]; UpdataHeap1(heap,0,20);//更新堆 } } } for (i=0;i<K;++i) { cout<<result[i]<<" "<<endl; } }
求数组最大k个数的问题(堆的应用)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。