堆排序从二叉树演化而来。
堆,分为大根堆和小根堆;
大根堆:一个特殊的完全二叉树,他的父节点一定比子节点大;
小根堆:父节点一定比子节点小;
下面的例子都是用大根堆
有两个重点
1.堆的向下调整
树的根节点的左右都是堆,但自己不是堆,这种时候可以通过向下调整,成为堆。
图1,需要向下调整
图2,将根节点2与它的子节点9和7比较,都比他大,将更大的往上提,2放到9的位置,继续跟8和5比较,以此类推
图3,最终形成堆
2.如何构建堆
一个无序的树,怎么构建成堆?
图1 是一个无序的树,首先我们找到第一个非叶子节点(从后往前找),这里是3
发现3的叶子节点是5,比它大,不符合大根堆条件,因此对3-5这个子树,做一个堆的向下调整操作,变成5-3
因为 9 这个节点 的叶子节点都比它小,所以不需要调整,我们看1这个节点,需要向下调整
再看8这个节点,比9小比5大,因此调整
最后调整6,也就是根节点,一个有序的堆就构建完成了。
原文:https://www.cnblogs.com/luyShare/p/14811499.html