/*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進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
