【数据结构:排序算法】堆排序(图文详解)

我们的五年 2024-07-10 12:05:05 阅读 84

🎁个人主页:我们的五年

🔍系列专栏:数据结构课程学习

🎉欢迎大家点赞👍评论📝收藏⭐文章

目录

🍩1.大堆和小堆

🍩2.向上调整算法建堆和向下调整算法建堆:

🍟向上调整算法:

🍟向下调整算法:

🍟用这两种方法建堆的时间复杂度:

🍩3.堆排序:


 

🍩1.大堆和小堆

要想弄明白堆排序,我们先来看看大堆和小堆的概念和区别: 

注意:堆是完全二叉树。

大堆:父节点都大于孩子节点。

小堆:父节点都小于孩子节点。

🍩2.向上调整算法建堆和向下调整算法建堆:

注:根节点我定为0

🍟向上调整算法:

向下调整算法调整该节点的前提是该节点以上的树已经是堆(大堆或者小堆),但是开始的时候,树里面的元素是随便放置的,但是可以把根元素以上看成一个堆,然后向上调整从2*0+1(第二层左边的元素)的位置开始就可以了。


以向上调整建立大堆为例:

从已经建好的堆的下一层开始向上调整,这里可以把根看成小堆,要想把整个二叉树调整为小堆形式,我们就要从根的下一层,把每个元素都进行一次向上调整。

向上调整的实现:

根该节点开始,我们把该节点与它的父节点进行比较,因为该节点以上的节点已经是大堆,此时的根是该树最大元素,所以只要和根比较谁大,如果比根大就交换位置,这样增加一个元素以后,该树还是大堆。

从上面图来看,向上调整结束的条件为该节点到达根节点,上面没有元素了。

由孩子节点的下标找到父节点的下标是:parent=(child-1)/2。

实现代码:

<code>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;

}

}

}

🍟用这两种方法建堆的时间复杂度:

假如待排序的二叉树有K层,假设为满二叉树:

如果用向上调整算法,那么进行的次数是:

第1层:2^0*0        //2的0次方这这一层的节点个数,0是调整的次数,根节点向上调整的时候 ,不需要调整。

第2层:2^1*1

……

第K层:2^(k-1)*k-1

所以总的次数为:

2^0*0+2^1*1+2^2*2+……+2^(k-1)*k=(k-1)*2^k-2.

个数N=2^k-1.k=log2 (N+1)

所以O(N)=(log2 (N+1)-1)*(N+1)-2。

数量级在log N

所以O(N)=N*log N。

向下调整:

其实用向下,就可以让节点最多的调整次数最少,也就是:多*少,少*多。

而向上调整,就是:多*多,少*少。第一层的节点少,不用调整,第二层两个节点,每个调整一次,后面节点多,每个节点调整次数也多。

第k-1层:2^(k-2)*1。

第k-2层:2^(k-3)*2。

……

第2层2^1*(k-2)。

第1层2^0*(k-1)。

总的:2^0*(k-1)+2^1*(k-2)+……+2^(k-2)*1=2^k+2*k-4。

O(N)=log N。

根据上面的结论,我们知道如果要建堆,那肯定是用向下调整更好。

🍩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;

}

}



声明

本文内容仅代表作者观点,或转载于其他网站,本站不以此文作为商业用途
如有涉及侵权,请联系本站进行删除
转载本站原创文章,请注明来源及作者。