建堆的时间复杂度：
假设树的高度为h，则每一层最多有2^(h-1)个结点
需要移动的结点的总数T(n)为：
堆的排序：
1.构建堆之后，就可以对数组进行排序了，堆顶元素在整个堆里是最小值。如果要将数组升序排列，小的在前，大的在后，需要建立大堆还是小堆呢？
需要建立大堆，因为如上图构建小根堆的结果，尽管1是堆顶元素，同时也是整个堆中最小的元素，但是整棵树不是按结点编号依次递增的，而顺序是{1,2,3,4,8,6,7,5}，因此小堆并不能对数组进行升序排列。所以，如果要将数组进行升序排列，要用大堆；同理，如果要将数组进行倒序排列，要用小堆。
2.为什么要使用大堆对数组进行升序排列？
（1）如果使用小堆对数组进行升序排列，那么对于数组，要选出最小的数，需要花费O(N)的时间，接着再选出次小的数，又需要花费O(N)的时间，那么数组排序的时间复杂度为O(N^2)，效率低。
（2）如果使用小堆输出堆顶第一个元素，那么剩下的元素父子关系有可能全乱了，又需要重新建堆，效率太低。
3.如何使用大堆对数组进行排序？
使用堆排序的目的是为了保持父子间的关系不要变，父亲永远是父亲，孩子永远是孩子，这样就不需要重建堆，最多只需要调整。
构造大根堆之后，堆顶元素是整个数组中的最大值，将堆顶元素与最后一个叶子结点进行交换，那么数组最后一个元素就是有序的；再将堆进行向上调整，堆顶元素为次大元素，将堆顶元素与倒数第二个叶子节点进行交换，数组最后两个元素是有序的，······直到堆输出最后一个元素。
如数组{6,8,5,9,3,7,2}要进行升序排序，先进行堆的构造，再进行堆排序
（1）大根堆的构造
第1步：倒数第一个非叶子结点的下标为(n-1-1)/2，即(5-1-1)/2=2，从倒数第一个非叶子结点编号为2的结点5开始作为子树向下调整，5的两个孩子7和2，7大，交换5和7
第2步：得到如下二叉树，对前一个编号1的位置即结点8作为子树向下调整，8的两个孩子9和3，9大，交换8和9
第3步：得到如下二叉树，对前一个编号0的位置即结点6进行向下调整，6的两个孩子9和3，9大，交换8和9
第4步：得到如下二叉树，此时以6位根节点的子树不满足大堆定义，需要进行向下调整，6的两个孩子8和3，8大，6和8进行交换。
第4步：得到如下二叉树，此时整棵树已经是大根堆了，调整完毕。
（2）堆的排序
第1步：将堆顶元素9与最后一个叶子结点2进行交换，这时9作为堆中最大的元素在数组最后，有序。但交换之后，2作为根结点，树已经不满足大堆的定义了，需要进行向下调整，2的两个孩子8和7，8大，交换2和8（9已经是有序的数组元素了，无需参与堆调整，以下同理）
得到如下二叉树，2作为根结点，还不满足大堆的定义，需要向下调整，2的两个孩子6和3，6大，交换2和6
第2步：得到如下大根堆
将堆顶元素8和倒数第一个叶子结点5进行交换，5作为根结点，树已经不满足大堆的定义了，需要进行向下调整，5的两个孩子8和7，7大，交换5和7
第3步： 得到如下大根堆，
将堆顶元素7和倒数第一个叶子结点3进行交换，3作为根结点，树已经不满足大堆的定义了，需要进行向下调整，3的两个孩子6和5，6大，交换3和6
第4步：得到如下大根堆 ，
将堆顶元素6和倒数第一个叶子结点2进行交换，2作为根结点，树已经不满足大堆的定义了，需要进行向下调整，2的两个孩子3和5，5大，交换2和5
第5步：得到如下大根堆
将堆顶元素5和倒数第一个叶子结点2进行交换，2作为根结点，树已经不满足大堆的定义了，需要进行向下调整，2只有一个孩子3，3大，交换2和3
第6步：得到如下大根堆
将堆顶元素3和倒数第一个叶子结点2进行交换
第7步： 得到如下堆，堆里只有一个元素2，满足大根堆定义，不需要调整，将堆顶元素2和最后一个叶子结点2进行交换
得到最终的二叉树为
此时的二叉树为数组的升序排列的逻辑结构，数组的物理结构为：
堆排序时间复杂度：
把第1个结点挪到正确的位置需要log(n)
把第2个结点挪到正确的位置需要log(n)
······
把第n个结点挪到正确的位置需要log(n)
因此堆排序的时间复杂度为nlog(n)
堆的插入：
（1）先将元素插入到堆的末尾，即最后一个叶结点之后
（2）如果堆的性质遭到破坏，将新插入节点，顺着其双亲向上调整到合适位置
堆的删除：
（1）将堆顶元素与堆中最后一个元素进行交换
（2）删除堆中最后一个元素
（3）将堆顶元素向下调整到满足堆的定义即可
堆面试题：
1. 1.下列关键字序列为堆的是：（） 2. A 100,60,70,50,32,65 3. B 60,70,65,50,32,100 4. C 65,100,70,32,50,60 5. D 70,65,100,32,50,60 6. E 32,50,100,70,65,60 7. F 50,100,70,65,60,32 8. 9. 答案为A，分析如下：
1. 2.已知小根堆为8,15,10,21,34,16,12，删除关键字 8 之后需重建堆，在此过程中，关键字之间 2. 的比较次数是（）。 3. A 1 4. B 2 5. C 3 6. D 4 7. 8. 答案为C，分析如下：
1. 3.一组记录排序码为(5 11 7 2 3 17),则利用堆排序方法建立的初始堆为 2. A(11 5 7 2 3 17) 3. B(11 5 7 2 17 3) 4. C(17 11 7 2 3 5) 5. D(17 11 7 5 3 2) 6. E(17 7 11 3 5 2) 7. F(17 7 11 3 2 5) 8. 9. 答案为C，分析如下：根据选项可以看出想要建立大根堆，数组要排升序
1. 4.最小堆[0,3,2,5,7,4,6,8],在删除堆顶元素0之后，其结果是（） 2. A[3，2，5，7，4，6，8] 3. B[2，3，5，7，4，6，8] 4. C[2，3，4，5，7，8，6] 5. D[2，3，4，5，6，7，8] 6. 7. 答案为C，分析如下：
