(1)从1000个数据中找到k个大数据
创新互联专注于仪陇企业网站建设,成都响应式网站建设公司,购物商城网站建设。仪陇网站建设公司,为仪陇等地区提供建站服务。全流程按需求定制开发,专业设计,全程项目跟踪,创新互联专业和态度为您提供的服务首先看到这个题时,可能会想到先将这1000个数据进行降序排序,即取出的前k个元素大。时间复杂度为O(N^2),使得程序效率低。
如何解决这个问题呢?我们的堆就派上用场喽!
解题思路:
可先创建一个数组topK[k],将100w中的前k个数据放入数组topK中,将topK中的数据建小堆,则可保证堆的第一个元素是最小的,将第k个元素与堆中第一个元素比较,若大于,则交换。对堆进行重新建小堆,取第k+1个元素与堆中第一个元素比较,以此类推,直至100w-k个元素比较完。则此时堆中的元素就是k个大数据。
代码实现:
const int N = 1000; const int K = 100; void AdjustDown(int topK[],int parent) //建小堆 { int child = 2*parent+1; while(child < K) { if(child+1 < K && topK[child+1] < topK[child]) { ++child; } if(topK[child] < topK[parent]) { swap(topK[child],topK[parent]); parent = child; child = 2*parent+1; } else { break; } } } void GetTopK(int a[],int topK[]) { assert(a); int i = 0; for(i=0;i=0;--i)//对前K个元素建小堆 { AdjustDown(topK,i); } for(i=K;i topK[0]) //将K个元素之后的每个元素和堆的第一个元素(最小元素)比较 { swap(a[i],topK[0]);//若比第一个元素大,则交换 AdjustDown(topK,0);//对新堆重新建小堆 } } }
测试代码:
void Test2() { int topK[K]; int a[N]; srand(time(0)); //随机数种子 for(int i=0;i测试结果:
时间复杂度为 k*lgk+N*lgk
当N庞大时,k可忽略,则时间复杂度为O(N),大大提高了效率。
(2)堆排序
既然是排序,那就有两种可能升序or降序。使得堆是建大堆方便还是建小堆方便。
<1>若为升序,则需要建大堆。
堆的第一个元素为大,将大元素与末尾元素交换,剩下的元素(除末尾元素)向下调整。
<2>若为降序,则需要建小堆。
堆的第一个元素为最小,将最小元素与末尾元素交换,剩下的元素(除末尾元素)向下调整。
代码实现(以升序为例):
void AdjustDown(int a[],int parent,int size) //建大堆 { assert(a); int child = 2*parent+1; while(child < size) { if(child+1 < size && a[child+1] > a[child]) { ++child; } if(a[child] > a[parent]) { swap(a[child],a[parent]); parent = child; child = 2*parent+1; } else { break; } } } void HeapSort(int a[],int size) { assert(a); //建堆 for(int i=(size-2)/2;i>=0;--i) { AdjustDown(a,i,size); //建大堆 } //选择大的放到末尾,从剩下数据向下调整 for(int i=0;i测试结果:
创新互联www.cdcxhl.cn,专业提供香港、美国云服务器,动态BGP最优骨干路由自动选择,持续稳定高效的网络助力业务部署。公司持有工信部办法的idc、isp许可证, 机房独有T级流量清洗系统配攻击溯源,准确进行流量调度,确保服务器高可用性。佳节活动现已开启,新人活动云服务器买多久送多久。
文章题目:堆的应用(1000个数据中找最大的前K个元素,堆排序)-创新互联
网页链接:http://www.cdkjz.cn/article/dhsieo.html