大数据处理堆实现N个数据找K个最大数据和堆排序

在N个数据中找K个最大数据思想：用堆实现找最大的数据，则先建立一个N个数据中其前K个节点的最小堆，将没进入最小堆的节点依次与小堆的头节点比较，若大于头节点，则替换两个值，并且调用向下调整算法（其思想前面博客已经介绍实现），直到N个数据比较完成，此时最小堆中的K个节点即为N个数据中的K个最大数据。

在代码中为了方便测试N与K的值较小。

堆排序思想：即建立一个堆来实现排序，升序与降序思想基本相同，这里介绍降序，要降序则先建立一个最小堆后，则每次将最小堆头节点与尾节点值交换，即最后一个节点为最小值，此时除去最后一个节点，在剩下范围调用向下调整算法，在依次用相同方法实现直至范围只剩下一个节点即为最大的一个节点。此时则排序完成。

代码实现：

#include <iostream>
#include <cstdlib>
#include <assert.h>
using namespace std;
void AdjustDown(int* a,size_t k,size_t i)  //向下调整
{
assert(a);
size_t parent=i;
size_t child=i*2+1;
while(child<k)
{
if(child+1<k&&a[child+1]<a[child])
++child;
if(a[child]<a[parent])
{
swap(a[child],a[parent]);
parent=child;
child=parent*2+1;
}
else
break;
}
}

void GetTopK(int* a,int* TopK,size_t n,size_t k) //N个数据找最大的前K个
{
for(size_t i=0;i<k;++i)
{
TopK[i]=a[i];
}
//先找第一个非叶子结点，依次向下调整建小堆
for(int i=(k-2)/2;i>=0;--i)
{
AdjustDown(TopK,k,i);
}
//选最大的前K个数据
for(size_t i=k;i<n;++i)
{
if(a[i]>TopK[0])
{
TopK[0]=a[i];
AdjustDown(TopK,k,0);
}
}
}

void HeapSort(int a[],size_t n)  //堆排序:降序
{
//建小堆
for(int i=(n-2)/2;i>=0;--i)
{
AdjustDown(a,n,i);
}
//交换调整
int end=n-1;
while(end>0)
{
swap(a[0],a[end]);
AdjustDown(a,end,0);
--end;
}
}
void TestNK()
{
const int N=1000;
const int K=5;
int a[N]={0};  //存储N个数据
int TopK[K]={0};  //存储K个最大数据
for(size_t i=0;i<N;++i)
{
a[i]=rand()%N;
}
a[10]=1000;
a[100]=2000;
a[200]=3000;
a[300]=4000;
a[400]=5000;

GetTopK(a,TopK,N,K);
for(size_t i=0;i<K;++i)
{
cout<<TopK[i]<<" ";
}
cout<<endl;
}

void TestHeapSort()
{
int a[]={19,17,18,14,16,13,15,12,10,11};
HeapSort(a,sizeof(a)/sizeof(a[0]));
}

int main()
{
TestNK();
TestHeapSort();
system("pause");
return 0;
}