Tanky WooRSS

《算法导论》学习总结 --- 4.第六章(1) 堆排序

14 Apr 2011
这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。

建议先看看前言:http://www.wutianqi.com/?p=2298

首先介绍几个概念:

卫星数据:一个带排序的的数通常是有一个称为记录的数据集组成的,每一个记录有一个关键字key,记录的其他数据称为卫星数据。

原地排序:在排序输入数组时,只有常数个元素被存放到数组以外的空间中去。

在第二章介绍了两种排序:插入排序和合并排序,接下来两章要介绍的是推排序和快速排序,这四个排序都属于比较排序(comparison sort)。

我以前总结过堆排序,并具体实现了堆排序,代码中给出了详细的注释,所以在这里就不重复发了,大家可以去看看,个人觉得总结的还是比较给力的:

http://www.wutianqi.com/?p=1820
这里再补充几点:

1.区别length[A]和heap-sort[A]。(P73)(这个在下一篇的优先级队列中将会具体区别)

2.总体上看堆排序由三个函数组成:①.MAX-HEAPIFY ②.BUILD-MAX-HEAP ③.HEAP-SORT

另外,在这里给大家补充一点个人经验,有时理论难以理解,代码难以理解,这个时候,就要靠秘诀了:拿起手中的笔和纸,自己给出一组输入,按照书上的代码,自己去模拟这组输入的执行过程。(这个过程人人都知道,但并不是人人都去做了!学算法,就要自己去模拟,去画图,去推!怎么样容易理解就怎么去做!)

所以这也是我喜欢《算法导论》的原因,接下来,就要强烈推荐大家看《算法导论》上非常非常给力的堆排序实现图了---图6-4。

总结:本章最基础也是最重要的就是理解堆这种结构!

堆是什么?来看看《算法导论》上的图6-1:

dui

图(a)是一个最大堆,图(b)是最大堆的数组表示。可以看到堆的数组并不是已排序好的。

让我们来回忆下最大堆的定义(P74):

在最大堆中,最大堆特性是指除了根以外的每个结点i,有A[PARENT(i)] >= A[i]。这样,堆的最大元素就存放在根结点中。

对,堆排序就是利用的这个特性---“堆的最大元素就存放在根结点中”

每次堆化,这样就找到了当前堆的最大元素。

所以说,理解了其本质特征,堆排序其实很简单的。

至于堆排序的具体应用,在后面的最短路算法---Dijkstra中,会用到由堆来优化普通的Dijkstra算法。

下一篇将实现最大优先级队列。

Tanky Woo 标签: 堆排序最大堆