在一百万个数据中，求出最大的k个数字，怎么效率高。
1. 将一百万个数据排序，承接上一篇的堆排序，时间复杂度为O(N * LogN)。但是显然这并不是最优解。
2. 一百万个数据放入一个数组中，将其视为一个完全二叉树，并用向下调整算法将其调整为一个大堆/小堆，然后Top/Popk次，即可求出前K个最大/最小的数字，时间复杂度为：O（N + K*LogN）
3. 用正确的堆处理TopK算法： 先假设求最大的K个数字，则建立大小为K的小根堆，然后在一百万-k个数据中，逐个遍历，若某个数据比小根堆的堆顶元素大，则替换掉堆顶元素，然后向下调整，使得这个堆重新变回一个小根堆。 时间复杂度为:O(K + (N-k)*LogK)
其实相较于2，3并没有时间上的很大提升，但是3在空间复杂度上有了巨大提升，2的空间为O(N),3为O(K)。 折中思考，3方法是求数据量较大的数据集合中前K个最大值/最小值的最佳方法
求K个最大值，建小堆，是因为，若遍历途中遇到了那K个数中的某一个，他一定比堆顶元素大，然后替换进去之后，向下调整，可以使得这个数字置于这个小根堆的底部。从而达到目的。
void AdjustUp(int* a, int child)
{
int parent = (child - 1) / 2;
while (child > 0)
{
if (a[child] > a[parent])
{
swap(a[parent], a[child]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
void AdjustDown(int* a,int size, int parent) // size 是总大小，parent是从哪里开始向下调整
{
int child = parent * 2 + 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 = parent * 2 + 1;
}
else
{
break;
}
}
}void Print_Heap_Topk(int* a, int n, int k)
{
int* KMaxHeap = new int[k]; // 最大堆存最小的K个数
for (int i = 0; i < k; ++i)
{
KMaxHeap[i] = a[i];
}
for (int i = (k - 1 - 1) / 2; i >= 0; --i)
{
AdjustDown(KMaxHeap, k, i);
}
for (int i = k; i < n; ++i)
{
if (a[i] < KMaxHeap[0])
KMaxHeap[0] = a[i];
AdjustDown(KMaxHeap, k, 0);
}
for (int i = 0; i < k; ++i)
{
cout << KMaxHeap[i] << " ";
}
cout << endl;
}
void test_topk()
{
int n = 10000;
int* a = new int[n];
srand(time(0));
for (int i = 0; i < n; ++i)
a[i] = rand() % 1000000;
a[5] = 1000000 + 1;
a[1231] = 1000000 + 2;
a[531] = 1000000 + 3;
a[5121] = 1000000 + 4;
a[120] = 1000000 + 5;
a[99] = 1000000 + 6;
a[0] = 1000000 + 7;
a[76] = 1000000 + 8;
a[423] = 1000000 + 9;
a[3144] = 1000000 + 10;
a[333] = -100;
a[999] = -200;
a[777] = -500;
a[888] = -800;
a[111] = -1000;
a[798] = -1;
a[1111] = -250;
a[2222] = -350;
a[3333] = -450;
a[4444] = -550;
Print_Heap_Topk(a, n, 10);
}
int main()
{
test_topk();
return 0;
}
