C++100w个数中找出最大的前K个数

/*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;

}

亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>