版本记录

版本号	时间
V1.0	2017.08.22

前言

将数据结构和算法比作计算机的基石毫不为过，追求程序的高效是每一个软件工程师的梦想。下面就是我对算法方面的基础知识理论与实践的总结。感兴趣的可以看上面几篇。
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。

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