了解堆的操作
和向上(下)调整算法
可以看我的上一篇文章:
详解(实现)堆的接口函数
文章目录
- 堆是什么?
- 堆排序的原理
- 如何建堆?怎样建堆更快?
- 1.使用向上调整算法建堆
- 时间复杂度分析
- 2.使用向下调整算法建堆
- 时间复杂度分析
- 结论:使用向下调整算法建堆更好
- 堆排序的实现
- 堆排序的时间复杂度
- 堆排序的稳定性
堆是什么?
堆排序,堆排序,首先就要知道堆是什么
堆是顺序存储逻辑结构是二叉树的特殊数据结构
如下图:
堆只有大堆(大顶堆)和小堆(小顶堆)
大堆:左右孩子节点中存储的数据都必须小于等于
父亲节点,根节点最大
小堆:左右孩子节点中存储的数据都必须大于等于
父亲节点,根节点最小
了解堆的操作
和向上(下)调整算法
可以看我的上一篇文章:
详解(实现)堆的接口函数
堆排序的原理
根据堆的特点:
堆只有大堆(大顶堆)和小堆(小顶堆)
大堆:左右孩子节点中存储的数据都必须小于等于
父亲节点,根节点最大
小堆:左右孩子节点中存储的数据都必须大于等于
父亲节点,根节点最小
可知大(小)堆堆顶的数据一定是堆中存储的所有元素中最大(小)的
所以我们只需要将堆顶数据(顺序表第一个元素)和堆的最后一个元素交换(顺序表最后一个元素),
堆中的最大(小)的元素就到了顺序表的最后
虽然交换之后的顺序表不是堆了,但是只需要将交换到堆顶的数据,进行一次向下调整算法,得到的就又是一个大(小)堆,而且一次向下调整算法的时间复杂度只有O(logN)
再将顺序表的倒数第二个元素当做新的最后一个元素,与调整后新的堆顶换…………
如此循环
我们就可以得到一个有序表了
由上得:
排升序,建大
堆
排降序,建小
堆
如何建堆?怎样建堆更快?
根据堆排序的原理可得:
实现对排序之前,要先将要排序的数据建堆
那么如何建堆?
有两个方法建堆
1.使用向上调整算法建堆
将要排序的数据从头到尾一个一个进行向上调整算法即可
时间复杂度分析
由上图得:
每一层的节点向上调整的最大次数不一样,所以要分开加算
总的调整次数为F(h):
F(h)=20 X 0+ 21 X 1+22 X2+…………+2(h-1) X(h-1)
使用错位相减法后,化简得:
F(h)=2h X(h-2)+2
由完全二叉树的特性得:
h=log N
2h-1=N
带入F(h)得
F(h)=(N+1)*(logN-2)+2
所以时间复杂度为:O(N*logN)
2.使用向下调整算法建堆
从最后一个非叶子
节点开始调整,调整到顺序表第一个元素(下标为0的元素)
时间复杂度分析
由上图得:
每一层的节点向上调整的最大次数不一样,所以要分开加算
总的调整次数为F(h):
F(h)=20 x(h-1) +21 x(h-2)+…………+2(h-2)x1+2(h-1)x0
使用错位相减法后,化简得:
F(h)=2h-1-(h-1)
由完全二叉树的特性得:
h=log N
2h-1=N
带入得
F(N)=N-logN
所以时间复杂度为:O(N)
结论:使用向下调整算法建堆更好
堆排序的实现
循环上图的过程,即可得到一个有序表
堆排序的时间复杂度
如下图:
所以堆排序总的时间复杂度为O(N*logN)
堆排序的稳定性
堆排序并不是
一个稳定的排序算法
在堆排序的过程中,当交换了堆顶元素后,进行向下调整时,有可能破坏了相同元素之间的稳定性。
例如,第n/2个父节点可能交换了后面一个元素,而第n/2-1个父节点没有交换后面一个相同的元素,这样就破坏了这两个相同元素之间的稳定性。
以上就是全部内容了,如果对你有帮助的话可以点赞收藏支持一下!