十种排序算法——堆排序(小顶堆)
首先要了解什么是堆?小顶堆又是什么?而堆排序是十种排序种唯一种自定义的数据结构
这里的堆就是我们所熟悉的二叉树
而小顶堆又是什么呢?
小顶堆就是根节点比子节点小,子节点比叶子节点小。
所以我们第一步是进行堆化,从它倒数第一个子节点进行堆化(从右到左)
它检查完了之后它的兄弟节点再检查
在进行交换子节点始终比叶子节点小
当交换完成之后再返回它的父节点进行检查
请注意在每次交换完成之后好要下沉,看一下它的子节点或者是叶子节点是否有比它小的
当下沉完成之后,同理在检查它的兄弟节点
当检查完之后再返回它的子节点,子节点进行下沉
到这里我们堆化完成了接下来