/*100w个数中找出最大的前K个数*/

从网站建设到定制行业解决方案，为提供成都网站设计、成都网站建设、外贸网站建设服务体系，各种行业企业客户提供网站建设解决方案，助力业务快速发展。创新互联将不断加快创新步伐，提供优质的建站服务。

#include

using namespace std;

#include

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<

if (i%5 == 0)

{

cout<

}

}

cout<

}

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;

}

网页名称：C++100w个数中找出最大的前K个数
URL分享：http://cdweb.net/article/ghhhhe.html