/*****************************
复杂度:
***************************/
#include<iostream>
#include<assert.h>
#include<vector>
#include<stdlib.h>
#include<time.h>
using namespace std;
#define N 1000
#define K 100
void AdjustDown(int *a, size_t root, size_t size)
{ //向下调整小堆
size_t parent = root;
size_t child = parent * 2 + 1;
while (child < size)
{
if (child + 1 < size && a[child] > a[child + 1])
{
++child;
}
if (a[parent] > a[child])
{
swap(a[parent], a[child]);
parent = child;
child = parent * 2 + 1;
}
else//注意不满足交换条件时跳出本次循环
{
break;
}
}
}
void GetTopk(const vector<int>& Vnumber, int n, int k)//N个数中找最大的前k个数--小堆实现
{
assert(n>k);
int *TopkArray = new int[k];//通过前k个元素建立含有k个元素的堆
for (size_t i = 0; i < k; i++)
{
TopkArray[i] = Vnumber[i];
}
for (int i = (k - 2) / 2; i >= 0; --i)//建小堆
{
AdjustDown(TopkArray, i, k);
}
//从第k个元素开始到第n个元素分别与堆顶元素进行比较,较大数据入堆顶,再对整个堆进行下调,使堆顶存放最小元素(小堆)
for (size_t i = k; i < n; ++i)
{
if (Vnumber[i] > TopkArray[0])
{
TopkArray[0] = Vnumber[i];
AdjustDown(TopkArray, 0, k);
}
}
size_t count = 0;
for (size_t i = 0; i < k; ++i)//打印k个最大数据,即堆中所有元素
{
cout << TopkArray[i] << " ";
++count;
if (count % 10 == 0)
{
cout << endl;
}
}
cout << endl;
delete[] TopkArray;//注意释放TopkArray所占的内存
TopkArray = NULL;
}
void CreateVnumber(vector<int>& Vnumber)//创建N个数
{
srand((unsigned int)time(NULL));
//srand(time(0));
Vnumber.reserve(N);
for (size_t i = 0; i<N; i++)
{
Vnumber.push_back(rand() % 1000);//产生N个随机值
}
for (size_t i = K; i < N; ++i)
{
Vnumber[i] *= 100;
}
}
int main()
{
vector<int> Vnumber;
CreateVnumber(Vnumber);
GetTopk(Vnumber, N, K);
//int length = Vnumber.size();
//for(int i=0;i<length;i++)
//{
// cout<<Vnumber[i]<<" ";
// }
return 0;
}