/*100w个数中找出最大的前K个数*/
#include <iostream>
using namespace std;
#include <assert.h>
const int N = 10000;
const int K = 100;
void AdjustDown(int topK[], int size, size_t parent)
{
assert(topK);
int child = parent*2 + 1;
while (child < size)
{
if (child+1 < size
&& topK[child+1] < topK[child])
{
++child;
}
if (topK[child] < topK[parent])
{
swap(topK[child], topK[parent]);
parent = child;
child = parent*2 + 1;
}
else
{
break;
}
}
}
void GetTopKValue(int array[], int topK[])
{
assert(K < N);
for (int i = 0; i < K; ++i)
{
topK[i] = array[i];
}
//建小堆
for (int i = (K-2)/2; i >= 0; --i)
{
AdjustDown(topK, K, i);
}
for (int i = K; i < N; ++i)
{
if (array[i] > topK[0])
{
topK[0] = array[i];
AdjustDown(topK, K, 0);
}
}
for (int i = 0; i < K; ++i)
{
cout<<topK[i]<<" ";
if (i%5 == 0)
{
cout<<endl;
}
}
cout<<endl;
}
void Test()
{
int array[N] = {0};
int topK[K] = {0};
for (int i = 0; i < N; ++i)
{
array[i] = i;
}
array[9] = 111111;
array[99] = 1111111;
array[999] = 11111111;
GetTopKValue(array, topK);
}
int main()
{
Test();
return 0;
}
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
