【数据结构】找出N个数据中最大的前k个数据(利用堆排序)-创新互联
我们举例,假若从10000万个数里选出前100个大的数据。
目前创新互联公司已为成百上千的企业提供了网站建设、域名、虚拟空间、网站托管维护、企业网站设计、眉县网站维护等服务,公司将坚持客户导向、应用为本的策略,正道将秉承"和谐、参与、激情"的文化,与客户和合作伙伴齐心协力一起成长,共同发展。首先我们先分析:既然要选出前100个大的数据,我们就建立一个大小为100的堆(建堆时就按找大堆的规则建立,即每一个根节点都大于它的子女节点),然后再将后面的剩余数据若符合要求就插入堆中,不符合就直接丢弃该数据。
那我们现在考虑:确定是该选择大堆的数据结构还是最小堆的数据结构呢。
分析一下:
若选用大堆的话,堆顶是堆的大值,我们考虑既然要选出从10000万个数里选出前100个大的数据,我们在建堆的时候,已经考虑了大堆的特性,那这样的话大的数据必然在它顶端。假若真不巧,我开始的前100个数据中已经有这10000个数据中的大值了,那对于我后面剩余的10000-100的元素再想入堆是不是入不进去了!!!所以,选用大堆从10000万个数里选出前100个大的数据只能找出一个,而不是100个。
那如果选用最小堆的数据结构来解决,最顶端是最小值,再次遇到比它大的值,就可以入堆,入堆后重新调整堆,将小的值pass掉。这样我们就可以选出大的前K个数据了。言外之意,假若我们要找出N个数据中最小的前k个数据,就要用大堆了。
代码实现(对于大堆最小堆的代码,若有不明白的地方,大家可以查看我的博客http://10740184.blog.51cto.com/10730184/1767076):
#define _CRT_SECURE_NO_WARNINGS 1 #includeusing namespace std; #include void AdjustDown(int* a, int parent, int size) { int child = 2 * parent + 1; while (child < size) { if (child + 1 < size && a[child] > a[child + 1]) { child++; } if (a[parent]>a[child]) { swap(a[parent], a[child]); parent = child; child = 2 * parent + 1; } else { break; } } } void Print(int* a, int size) { cout << "前k个大的数据:" << endl; for (int i = 0; i < size; i++) { cout << a[i] << " "; } cout << endl; } int* HeapSet(int*a,int N,int K) { assert(a); assert(K > 0); int* arr = new int[K]; //将前K个数据保存 for (int i = 0; i < K; i++) { arr[i] = a[i]; } //建堆 for (int i = (K-2)/2; i >=0; i--) { AdjustDown(arr,i,K); } //对剩余的N-K个元素比较大小 for (int i = K; i < N; i++) { if (arr[0] 由此可以看出,时间复杂度为:K+(K-2)/2*lgn+(N-K)*lgn --> O(N)
空间复杂度为:K-->O(1)。
创新互联www.cdcxhl.cn,专业提供香港、美国云服务器,动态BGP最优骨干路由自动选择,持续稳定高效的网络助力业务部署。公司持有工信部办法的idc、isp许可证, 机房独有T级流量清洗系统配攻击溯源,准确进行流量调度,确保服务器高可用性。佳节活动现已开启,新人活动云服务器买多久送多久。
新闻名称:【数据结构】找出N个数据中最大的前k个数据(利用堆排序)-创新互联
地址分享:http://scyanting.com/article/csoppp.html