我们举例，假若从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
#include<iostream>
using namespace std;
#include<assert.h>
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]<a[i])
{
arr[0] = a[i];
AdjustDown(arr, 0, K);
}
}
return arr;
delete[] arr;
}
void Test()
{
int arr[] = { 12, 2, 10, 4, 6, 8, 54, 67, 25, 178 };
int k = 5;
int* ret = HeapSet(arr, sizeof(arr) / sizeof(arr[0]), k);
Print(ret, k);
}
int main()
{
Test();
system("pause");
return 0;
}由此可以看出，时间复杂度为：Ｋ＋（Ｋ-2）/２*lgn＋（Ｎ－Ｋ）*lgn --＞ O(N)
空间复杂度为：K-->O(1)。
亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
