题目描述
输入一串序列,对该序列进行堆排序
堆排序概念
- 堆排序是利用了堆(树)这个数据结构而设计的一种排序算法,堆排序是一种选择排序,他也是一个不稳定的算法
- 堆是具有以下性质的完全二叉树:每个结点的值都大于或者等于其左右孩子结点的值,称为大顶堆:==注意==:没有要求结点的左右孩子的值的大小关系
- 每个结点的值都小于或者等于其左右孩子结点的值,称为小顶堆
- 一般升序用大顶堆,降序采用小顶堆
- 堆排序适合关键字较多的情况,例如在1亿个数中选出前100个最大值;
输入样例
5 3
4 5 1 3 2
输出样例
1 2 3
时间复杂度
最好时间复杂度和最坏时间复杂度都一样为O(nlog2n)
参考文献
C代码
#include <stdio.h>
#include <stdlib.h>
//调整堆
void HeadAdjust(int* arr, int k, int len) {
arr[0] = arr[k];//暂存子树的根结点
for (int i = 2*k; i <= len; i *= 2)//指向左孩子,沿key较大的子节点向下筛选("下坠")
{
if (i < len && arr[i] < arr[i+1])//只有i<len的时候才能保证有右孩子,此时判断左右孩子更大
{
i++;//取较大的key的下标
}
if (arr[0] > arr[i])//表示当前根就是最大的,无须进行后序操作
{
break;
}
else
{
arr[k] = arr[i];//将arr[i]调整到双亲结点上
k = i;//修改K的值继续向下筛选("下坠")
}
}
arr[k] = arr[0];//被筛选的结点放入最终位置
}
//建立大根堆
void BuildMaxHeap(int* arr, int len) {
//建立大根堆时,只需要调整所有非叶子结点(i <= n/2)
for (int i = len/2; i > 0; i--)//从[n/2,1]反复调整堆
{
//对小元素不断"下坠"
HeadAdjust(arr, i, len);
}
}
//堆排序
void HeapSort(int* arr, int len) {
//因为是升序,所以建立大根堆
BuildMaxHeap(arr, len);
for (int i = len; i > 0; i--)
{
//第一个元素和堆底元素进行交换
int temp = arr[i];
arr[i] = arr[1];
arr[1] = temp;
HeadAdjust(arr, 1, i - 1);//调整,把剩余的i-1个元素整理成堆
}
}
int main() {
int n, m;
scanf("%d%d", &n, &m);
int* arr = (int*)malloc(sizeof(int) * (n+1));
for (int i = 1; i <= n; i++)
{
scanf("%d", &arr[i]);//下标为0的位置暂时不存,后序会使用到
}
HeapSort(arr, n);
for (int i = 1; i <= m; i++)
{
printf("%d ", arr[i]);
}
return 0;
}