版本记录

前言

将数据结构和算法比作计算机的基石毫不为过，追求程序的高效是每一个软件工程师的梦想。下面就是我对算法方面的基础知识理论与实践的总结。感兴趣的可以看上面几篇。
1. 算法简单学习（一）—— 前言
2. 算法简单学习（二）—— 一个简单的插入排序
3. 算法简单学习（三）—— 分治法与合并排序
4. 算法简单学习（四）—— 冒泡排序
5. 算法简单学习（五）—— 函数的增长
6. 算法简单学习（六）—— 常用的几种相关函数
7. 算法简单学习（七）—— 递归式
8. 算法简单学习（八）—— 堆排序

建堆

我们可以自底向下地用 MAX - HEAPIFY 来将一个数组A[1 ... n]变成最大堆。BUILD - MAX - HEAPIFY对树中的每一个结点都调用一次 MAX - HEAPIFY。下面看一下伪代码。

伪代码

下面这个图给出了BUILD - MAX - HEAPIFY作用过程的一个例子。

建堆过程1

建堆过程2

下面我们就详细的说一下这个建堆的过程，图中展示的是BUILD - MAX - HEAPIFY的第3行调用MAX - HEAPIFY之前的数据结构。

• a)一个包含10和元素的输入数组A及其所表示的二叉树，图中示出了调用MAX - HEAPIFY（A, i）之前循环下标 i 指向结点5。
• b) 结果所得的数据结构，循环下标 i 的下一轮执行张红指向结点 4。
• c) ~ e)BUILD - MAX - HEAPIFY中for循环的后续执行过程，注意当对某结点调用MAX - HEAPIFY时，该结点的两颗子树都已是最大堆。
• f) BUILD - MAX - HEAP执行完毕后的最大堆。

堆排序算法

堆排序算法首先用BUILD - MAX - HEAP将输入数组A[1 ... n]构成一个最大的堆，因为数组中最大元素在根A[ 1 ]，则可以用过它与A[ n ]互换来达到最终正确的位置。如果从堆中去掉结点n（通过减小heap - size[ A ]），可以很容易地将A[1 ... n - 1]建成最大堆，原来根的子女仍是最大堆，而新的根元素可能违背了最大堆性质，这时调用MAX - HEAPIFY（A, 1）就可以保持这一性质，在A[1 ... n - 1]中构造出最大堆，堆排序算法不断重复这个过程，堆的大小由n - 1一直降到2。

下面我们就看一下堆排序的伪代码。

堆排序伪代码

下图给出了在初始最大堆建立后堆排序的一个例子，图中的每个最大堆与算法第2 ~ 5 行的 for 循环的每一次迭代的开始对应。

HEAPSORT过程的时间代价为O(nlgn)，其中调用 BUILD - MAX - HEAP的时间为O(n)，n - 1次 HEAP - MAX - HEAPIFY调用中每一次的时间代价为O(lgn)。

堆排序过程1

堆排序过程2

堆排序过程3

下面我们就详述其过程：

• a) 用BUILD - MAX - HEAP构造所得的最大堆的数据结构。
• b) ~ j) 每次在第5行调用MAX - HEAPIFY后的最大堆，同时示出 i 的值，仅浅阴影结点仍然留在堆中。
• k) 结果的排序数组A。

后记

未完，待续~~~

秋