堆排序

今天下午有个大型招聘会在学交，好多人。。下午去做了讯飞的笔试。好多知识点都不清楚，不忍直视。。

堆

堆实际上是一棵完全二叉树，其任何一非叶节点满足性质：
任何一非叶节点的关键字不大于或者不小于其左右孩子节点的关键字。

堆排序的思想

1、将数据初始化成堆，即将数据存储到一个完全二叉树中，再构造大顶堆（升序）或小顶堆（降序）。
2、交换堆顶元素和最后一个元素，得到一个新的堆，被交换到底部的黄色部分为有序，其余堆为无序且可能不满足堆特性，所以需要对其余部分进行堆调整，调整好后继续将堆顶元素和最后一个堆低未排序元素进行交换……

复杂度
从上述过程可知，堆排序其实也是一种选择排序，是一种树形选择排序。只不过直接选择排序中，为了从R[1...n]中选择最大记录，需比较n-1次，然后从R[1...n-2]中选择最大记录需比较n-2次。事实上这n-2次比较中有很多已经在前面的n-1次比较中已经做过，而树形选择排序恰好利用树形的特点保存了部分前面的比较结果，因此可以减少比较次数。对于n个关键字序列，最坏情况下每个节点需比较log2(n)次，因此其最坏情况下时间复杂度为nlogn。堆排序为不稳定排序，不适合记录较少的排序

堆的存储：　一般用数组来表示堆，若根结点存在序号0处， i结点的父结点下标就为(i-1)/2。i结点的左右子结点下标分别为2i+1和2i+2。（注：如果根结点是从1开始，则左右孩子结点分别是2i和2i+1。）

---

参考原文
http://www.cnblogs.com/mengdd/archive/2012/11/30/2796845.html
http://www.cnblogs.com/dolphin0520/archive/2011/10/06/2199741.html