我要评论🎁个人主页：
🔍系列专栏：
🎉欢迎大家点赞👍评论📝收藏⭐文章
目录
🍩1.大堆和小堆
要想弄明白堆排序，我们先来看看大堆和小堆的概念和区别：
注意：堆是完全二叉树。
大堆：父节点都大于孩子节点。
小堆：父节点都小于孩子节点。
🍩2.向上调整算法建堆和向下调整算法建堆：
注：根节点我定为0
🍟向上调整算法：
向下调整算法调整该节点的前提是该节点以上的树已经是堆（大堆或者小堆），但是开始的时候，树里面的元素是随便放置的，但是可以把根元素以上看成一个堆，然后向上调整从2*0+1（第二层左边的元素）的位置开始就可以了。
以向上调整建立大堆为例：
从已经建好的堆的下一层开始向上调整，这里可以把根看成小堆，要想把整个二叉树调整为小堆形式，我们就要从根的下一层，把每个元素都进行一次向上调整。
向上调整的实现：
根该节点开始，我们把该节点与它的父节点进行比较，因为该节点以上的节点已经是大堆，此时的根是该树最大元素，所以只要和根比较谁大，如果比根大就交换位置，这样增加一个元素以后，该树还是大堆。
从上面图来看，向上调整结束的条件为该节点到达根节点，上面没有元素了。
由孩子节点的下标找到父节点的下标是：parent=（child-1）/2。
实现代码：
void adjustup(int* a,int child)
{
//该节点开始比较
int parent = (child - 1 - 1) / 2;
while (child > 0) //当节点到达根节点，就没有父亲节点了，就停止
{
if (a[parent] < a[child])
{
int tmp = a[parent];
a[parent] = a[child];
a[child] = a[parent];
child = parent;
parent = (child - 1 - 1) / 2;
}
else
{
break;
}
}
}🍟向下调整算法：
向下调整算法的要求就是左右子树已经是堆（大堆或者小堆）。结束的条件是孩子节点为null。
代码为：
void adjustdown(int* a, int size, int parent)
{
//假设法
int child = parent * 2 + 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 = parent * 2 + 1;
}
else
{
break;
}
}
}🍟用这两种方法建堆的时间复杂度：
根据上面的结论，我们知道如果要建堆，那肯定是用向下调整更好。
🍩3.堆排序：
用向下排序拍好序以后，如果我们要排升序，我们就建大堆，如果我们要排降序，我们就排小队堆。
升序：大堆。
降序：小堆。
我们以升序为例：
当得到大堆的时候，根节点是最大的，然后我们把根节点和最后的节点换一下位置，这样最大的就到最后面去了，然后我们换完以后，又用向下调整使除最后一个节点以外为大堆，这样我们取根节点，我们就的得到了第二大的，我们就把第二大的和数组的倒数第2的位置换位置，然后再让根节点向下调整建立大堆……
这样我们就能让数组升序,代码实现：
void swap(int* x, int* y)
{
int tmp = *x;
*x = *y;
*y = tmp;
}
void adjustdown(int* a, int size, int parent)
{
//假设法
int child = parent * 2 + 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 = parent * 2 + 1;
}
else
{
break;
}
}
}
//升序
void heapsort(int* a, int n)
{
for (int i = (n - 1 - 1) / 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;
}
}
发表评论