Date: 31 Jan 2015
最近一直在重新学习一些算法，有不少收获。在学习的同时突然想到应该用程序实现这些算法来巩固所学知识。这次在实现上选择了 Swift 语言，这样可以在巩固算法知识的同时还可以熟悉一下这门新的语言。还有一个原因就是借助 Swift 语言的 Playground 的功能可以更加清楚地观察算法每个步骤的表现。
堆排序利用了完全二叉树（complete binary tree）的索引所具有的规律把数组自然地组织成一个近似完全二叉树，从而通过不断修改和维护这个二叉树来达到排序的目的。二叉树的索引上有下面三个规律：
按照这些规律把数组中的索引看做是二叉树的索引，这样就可以把数组构造（看做）是一个近似完全二叉树了。堆排序最关键的步骤就是维护最大堆（Max-heapify）。Max-heapify 操作首先有一个假设：要进行 Max-heapify 操作的二叉树根节点的左右子树已经构成最大堆（Max-heap）了，这样在进行 Max-heapify 时 只要根节点和其左右字节点进行比较，如果根节点不是最大的，则和最大的子节点进行交换，进行交换后之前最大值的子节点所在的子树的最大堆就被破坏了，所以就要在这个子树上再进行 Max-heapify 操作，如此递归下去完成 Max-heapify 操作。了解了 Max-heapify 之后就可以进行堆排序了。对象排序可以分为两大步骤：
构建最大堆。 构建最大堆的方法是从数组的长度的一半作为索引开始对数组做 Max-heapify 操作，该索引不断递减直到数组的一个元素，每次递减后都对数组在该索引位置做 Max-heapify 操作。
排序。 最大堆构建完成后，首先从数组的最后一个元素开始与数组的第一个元素进行交换，这样最大元素就被排到了最后，并把这个元素从堆中去除，这样堆的大小减少了一，同时对改变后的堆在第一个元素的索引位置上进行 Max-heapify 操作 以维护最大堆。这样的交换一直进行下去，直到数组的第二个元素完成交接，同时排序也完成了。
总结：堆排序在运行时间和空间占用上几乎和快速排序一样，只是在实现上相对复杂一些。但是这个算法设计还是十分巧妙地，特别是在对二叉树节点性质的运用上。