初阶数据结构(C语言实现)——5.3 堆的应用(1)——堆排序
目录
- 1 堆的应用
- 1.1 堆排序
- 1.1.1 思路
- 1.1.2 代码实现
- 1.2 建堆的时间复杂度
- 1.2.1 向下调整
- 1.2.1 向上调整
- 1.2.3 结论
学习堆的应用之前,欢迎学习下堆。
这是博主之前的文章,欢迎学习交流
初阶数据结构(C语言实现)——5.2 二叉树的顺序结构及堆的实现
初阶数据结构(C语言实现)——5.1二叉树基础概念
1 堆的应用
1.1 堆排序
1.1.1 思路
堆排序即利用堆的思想来进行排序,总共分为两个步骤:
- 建堆
升序:建大堆
降序:建小堆 - 利用堆删除思想来进行排序
建堆和堆删除中都用到了向下调整,因此掌握了向下调整,就可以完成堆排序。
1.1.2 代码实现
void swap(HPDataType* p1, HPDataType* p2)
{
HPDataType x = *p1;
*p1 = *p2;
*p2 = x;
}
void AdjustUp(HPDataType* a, int child)
{
int parent = (child - 1) / 2;//根据孩子位置,计算父亲位置
while (child > 0)//child = 0,说明parent不存在了,已经到堆顶了
{
if (a[child] > a[parent]) //当孩子大小大于父亲大小的时候就交换
{
swap(&a[child], &a[parent]);//因为其他地方也要用到交换,封装了一个交换函数
child = parent; //现在把父亲的值给孩子。
parent = (child - 1) / 2;//继续计算现在节点的父亲结点,
}
else//孩子<=父亲 没必要往上走,直接break就行。
{
break;
}
}
}
void AdjustDown(HPDataType* a, int n ,int parent)
{
int child = parent*2+1;//根据父亲位置,计算孩子位置
while (child <n)//走到没有孩子的时候,结束,
{
// 选出左右孩子中大的那一个
if (child + 1 < n && a[child + 1] > a[child])//必须把child+1<n放前面,否则后面a[child+1]就越界了!
{
++child;
}
//交换
if (a[child] > a[parent])
{
swap(&a[child],&a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
// 排升序 -- 建大堆
void Heapsort(int* a, int n)//参数:数组和数据个数
{
//建堆,方法1:向上调整堆 //模拟的是插入数据的过程
for (int i = 1; i < n; ++i)
{
AdjustUp(a, i);
}
//建堆,方法2:向下调整堆
for (int i = 1; i < n; ++i)
{
AdjustDown(a, n , i);
}
int end = n - 1;
while (end > 0)
{
swap(&a[end], &a [0]);
AdjustDown(a, end, 0);
--end;
}
}
1.2 建堆的时间复杂度
1.2.1 向下调整
因为堆是完全二叉树,而满二叉树也是完全二叉树,此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值,多几个节点不影响最终结果):
因此:向下建堆的时间复杂度为O(N)。
1.2.1 向上调整
因此向上建堆的时间复杂度是N*logn
1.2.3 结论
向下调整时间复杂度更小,更优,所以建堆使用的是向下调整