(1)从1000个数据中找到k个最大数据
首先看到这个题时，可能会想到先将这1000个数据进行降序排序，即取出的前k个元素最大。时间复杂度为O（N^2）,使得程序效率低。
如何解决这个问题呢？我们的堆就派上用场喽！
解题思路：
可先创建一个数组topK[k],将100w中的前k个数据放入数组topK中，将topK中的数据建小堆，则可保证堆的第一个元素是最小的，将第k个元素与堆中第一个元素比较，若大于，则交换。对堆进行重新建小堆，取第k+1个元素与堆中第一个元素比较，以此类推，直至100w-k个元素比较完。则此时堆中的元素就是k个最大数据。
代码实现：
计算
安全
数据库
网络和加速
企业服务
const int N = 1000;
const int K = 100;
void AdjustDown(int topK[],int parent) //建小堆
{
int child = 2*parent+1;
while(child < K)
{
if(child+1 < K && topK[child+1] < topK[child])
{
++child;
}
if(topK[child] < topK[parent])
{
swap(topK[child],topK[parent]);
parent = child;
child = 2*parent+1;
}
else
{
break;
}
}
}
void GetTopK(int a[],int topK[])
{
assert(a);
int i = 0;
for(i=0;i<K;++i) //将a的前K个元素放入数组中
{
topK[i] = a[i];
}
for(i=(K-2)/2;i>=0;--i)//对前K个元素建小堆
{
AdjustDown(topK,i);
}
for(i=K;i<N;++i)
{
if(a[i] > topK[0]) //将K个元素之后的每个元素和堆的第一个元素(最小元素)比较
{
swap(a[i],topK[0]);//若比第一个元素大，则交换
AdjustDown(topK,0);//对新堆重新建小堆
}
}
}测试代码：
void Test2()
{
int topK[K];
int a[N];
srand(time(0)); //随机数种子
for(int i=0;i<N;++i)
{
a[i] = rand(); //随机数
}
GetTopK(a,topK);
for(int i=0;i<K;i++)
{
cout<<topK[i]<<" ";
}
}测试结果：
时间复杂度为 k*lgk+N*lgk
当N庞大时，k可忽略，则时间复杂度为O（N），大大提高了效率。
（2）堆排序
既然是排序，那就有两种可能升序or降序。使得堆是建大堆方便还是建小堆方便。
<1>若为升序，则需要建大堆。
堆的第一个元素为最大，将最大元素与末尾元素交换，剩下的元素（除末尾元素）向下调整。
<2>若为降序，则需要建小堆。
堆的第一个元素为最小，将最小元素与末尾元素交换，剩下的元素（除末尾元素）向下调整。
代码实现（以升序为例）：
void AdjustDown(int a[],int parent,int size) //建大堆
{
assert(a);
int child = 2*parent+1;
while(child < size)
{
if(child+1 < size && a[child+1] > a[child])
{
++child;
}
if(a[child] > a[parent])
{
swap(a[child],a[parent]);
parent = child;
child = 2*parent+1;
}
else
{
break;
}
}
}
void HeapSort(int a[],int size)
{
assert(a);
//建堆
for(int i=(size-2)/2;i>=0;--i)
{
AdjustDown(a,i,size); //建大堆
}
//选择最大的放到末尾，从剩下数据向下调整
for(int i=0;i<size;i++)
{
swap(a[0],a[size-1-i]);
AdjustDown(a,0,size-1-i);
}
}
//测试代码
void TestHeapSort()
{
int a[] = {10,16,18,12,11,13,15,17,14,19};
int size = sizeof(a)/sizeof(a[0]);
HeapSort(a,size);
}测试结果：
亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
