2022-02-11 堆排序与递归

摘要:
记录在研究堆排序时的心得.

堆排序:
堆排序也是基于比较的排序, 但是其思想基础来自于递归, 这点非常显著的区别于分治思想.
作为递归思想的经典体现, 有必要从堆排序的过程中总结出经验.

堆排序的伪代码:
CLRS

递归的结束, 关键点在第八行, 只有当找出的最大值的下标不是自己的时候, 才继续进行递归.
如果自己和左节点与右节点之间最大的, 则递归终止.
需要MAX-HEAPIFY只针对单个节点, 而非整个堆, 所以对于整个堆需要递归的调用MAX-HEAPIFY

TAOCP中的流程是这样的

堆排序分析:
从整体上思考, 那么堆排序可以抽象成, 某节点, 与其左节点和右节点之间关系的处理.
从堆顶开始进行, 则递归的处理每个点与其左节点和右节点.

考虑从堆顶开始, 则堆顶节点, 限定为整个堆最小的数据节点
-> 堆顶必须小于其左右两个子节点.
-> 堆顶的左右两个子节点, 必须小于相应节点的左右两个子节点

2022-02-11 堆排序与递归最先出现在Python成神之路。