2022-02-11 堆排序与递归_堆排序递归式

作者：不正经 | 2024-05-04 08:01:48

踩

堆排序递归式

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

堆排序也是基于比较的排序, 但是其思想基础来自于递归, 这点非常显著的区别于分治思想.

作为递归思想的经典体现, 有必要从堆排序的过程中总结出经验.

CLRS

递归的结束, 关键点在第八行, 只有当找出的最大值的下标不是自己的时候, 才继续进行递归.

如果自己和左节点与右节点之间最大的, 则递归终止.

需要MAX-HEAPIFY只针对单个节点, 而非整个堆, 所以对于整个堆需要递归的调用MAX-HEAPIFY

TAOCP中的流程是这样的

从整体上思考, 那么堆排序可以抽象成, 某节点, 与其左节点和右节点之间关系的处理.

从堆顶开始进行, 则递归的处理每个点与其左节点和右节点.

考虑从堆顶开始, 则堆顶节点, 限定为整个堆最小的数据节点

-> 堆顶必须小于其左右两个子节点.

-> 堆顶的左右两个子节点, 必须小于相应节点的左右两个子节点

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/不正经/article/detail/533488