堆排序算法之初始堆建立总结

堆排序算法之初始堆建立总结

@(算法学习)

关于堆的插入和删除有过一篇思考,但是关于初始堆的构建,没有总结。

简单说就下面几个要点(以大顶堆为例):

  • 首先根据序列构建一个完全二叉树
  • 在完全二叉树的基础上,从最后一个非叶结点开始调整:比较三个元素的大小–自己,它的左孩子,右孩子。分为三种情况:
    • 自己最大,不用调整
    • 左孩子最大,交换该非叶结点与其左孩子的值,并考察以左孩子为根的子树是否满足大顶堆的要求,不满足递归向下处理
    • 右孩子最大,交换该非叶结点与其右孩子的值,并考察以右孩子为根的子树是否满足大顶堆的要求,不满足递归向下处理

就这些基本要求,就可以解决这一类的手工计算问题。举个例子:

比如:一组记录(5,11,7,2,3,17)利用大顶堆排序方法建立初始堆为?

分析:首先建立完全二叉树。

《堆排序算法之初始堆建立总结》

再从最后一个非叶结点开始调整。

第一次交换7,17的位置。

《堆排序算法之初始堆建立总结》

11不用调整。

最后调整根结点。

《堆排序算法之初始堆建立总结》

此时把5换下去后,以5为根的子树不满足大顶堆的要求,因此再调整。

《堆排序算法之初始堆建立总结》

即最终的初始堆是:17,11,7,2,3,5.

    原文作者:排序算法
    原文地址: https://blog.csdn.net/u011240016/article/details/53428489
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞