《算法导论》学习总结 --- 4.第六章(1) 堆排序
首先介绍几个概念：
卫星数据：一个带排序的的数通常是有一个称为记录的数据集组成的，每一个记录有一个关键字key，记录的其他数据称为卫星数据。
原地排序：在排序输入数组时，只有常数个元素被存放到数组以外的空间中去。
在第二章介绍了两种排序：插入排序和合并排序，接下来两章要介绍的是推排序和快速排序，这四个排序都属于比较排序(comparison sort)。
我以前总结过堆排序，并具体实现了堆排序，代码中给出了详细的注释，所以在这里就不重复发了，大家可以去看看，个人觉得总结的还是比较给力的：
|
html">http://www.zzzyk.com/kf/201104/88127.html |
这里再补充几点：
1.区别length[A]和heap-sort[A]。(P73)(这个在下一篇的优先级队列中将会具体区别)
2.总体上看堆排序由三个函数组成：①.MAX-HEAPIFY ②.BUILD-MAX-HEAP ③.HEAP-SORT
另外，在这里给大家补充一点个人经验，有时理论难以理解，代码难以理解，这个时候，就要靠秘诀了：拿起手中的笔和纸，自己给出一组输入，按照书上的代码，自己去模拟这组输入的执行过程。(这个过程人人都知道，但并不是人人都去做了！学算法，就要自己去模拟，去画图，去推！怎么样容易理解就怎么去做！)
所以这也是我喜欢《算法导论》的原因，接下来，就要强烈推荐大家看《算法导论》上非常非常给力的堆排序实现图了—图6-4。
总结：本章最基础也是最重要的就是理解堆这种结构！
堆是什么？来看看《算法导论》上的图6-1：
图(a)是一个最大堆，图(b)是最大堆的数组表示。可以看到堆的数组并不是已排序好的。
让我们来回忆下最大堆的定义(P74)：
在最大堆中，最大堆特性是指除了根以外的每个结点i，有A[PARENT(i)] >= A[i]。这样，堆的最大元素就存放在根结点中。
对，堆排序就是利用的这个特性—“堆的最大元素就存放在根结点中”
每次堆化，这样就找到了当前堆的最大元素。
所以说，理解了其本质特征，堆排序其实很简单的。
至于堆排序的具体应用，在后面的最短路算法—Dijkstra中，会用到由堆来优化普通的Dijkstra算法。
下一篇将实现最大优先级队列。
补充：综合编程 , 其他综合 ,
