堆排序从二叉树演化而来。
堆，分为大根堆和小根堆；
大根堆：一个特殊的完全二叉树，他的父节点一定比子节点大；
小根堆：父节点一定比子节点小；
下面的例子都是用大根堆
有两个重点
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