目录
堆的定义
建立初始化堆的步骤
建立大根堆的代码
大根堆排序的代码
算法效率分析
稳定性
堆的定义
回忆
基于选择排序的特性：选取关键字最小（或者最大）的元素放入到序列里面，知道了大堆和小堆概念，所以将数组转换为二叉树用大小堆，进行选择排序比较方便
建立初始化堆的步骤
下面讲解给了初始序列（数组形式）如何转换为大根堆的样子来进行选择排序
非终端结点就是i<=n/2,即8/2=4，数组下标是01234的，后面的5678下标都是叶子结点不用管
调整后的样子如下
建立大根堆的代码
得到
09小元素下坠如下： （每次把最大的元素往上面放）09的左右子树当中右子树78最大，78上移
09还是小于左右子树，此时左子树65大于53，所以把65上移，09下坠到65的位置 得到如下：
完成了第一趟的处理，效果是把最大元素放到末尾，上面树成为大根堆的形式
第二趟
78和53交换
交换得到如下 78和87已经放到最后就暂时不用考虑了
53进行下坠，和65换位置得到如下： （78放到最后了不需要和53比较）
剩余元素成为了大根堆，如下所圈出来部分
第三趟
得到
下坠：
得到如下，所圈出来部分又是大根堆
依次类推，得到结果
大根堆排序的代码
算法效率分析
只需要记住建堆的过程，关键字对比次数不超过4n，建堆的时间复杂度=O（n）
稳定性
堆排序不稳定
