我们有意调整了排序的顺序，最后讲这个堆排序。不是因为它很难，而是它涉及到了基本的数据结构知识。
堆，又名“优先队列”，是一个带有优先级（就是一定顺序）的队列，而队列则是一种基础数据结构，它的特点是“先进先出”，i.e.，先进入队列的元素，在做移除操作时会被首先移除出队列。其实，优先队列这种队列，并没有说最先进入的会被最先移除，因为带有一定的顺序，首先进入的元素也会根据要求放到合适的位置，而不是最前端，而删除时，假设是默认删除，会删除最上方的元素。
我们的堆，一般情况下都是二叉堆，就是由完全二叉树构成的对象。二叉树是一种树形结构，每个父节点只有2个子节点；而完全二叉树则是说，在排下一个子节点时，必须保证这一层之前所有的位置都有节点。
这样的结构就会有以下几个特点，
- 假设一个元素的编号是 i，一个元素的2个子节点——左孩子和右孩子分别是 2i 和 2i+1。
- 其父节点的编号是 i/2，是向下取整的。
所以，当我们构建一个（最小）二叉堆时，我们首先需要一个基本数据结构——描述堆的struct或者class：
template <typename T>
struct Heap
{
int Capacity; //描述堆的能力，i.e.，堆一共能放几个数
int Size; //堆目前放了几个数
T *elements; //一个放置元素的数组
};
而我们在使用的时候，可以这样定义一下：
typedef struct Heap *PriorityQueue;
就会有一个指向此优先队列的指针。
而初始化这个优先队列也很简单，给指向优先队列的指针一个空间，给放置元素的数组开辟一个空间，给结构Heap一个初始值：
template<typename T>
PriorityQueue Initialize( int MaxSize )
{
PriorityQueue H;
H = malloc( sizeof( struct Heap ) ); //开辟指针的空间
if ( H == NULL )
Error( "out of space" ); //空间开辟失败
H->Elements = malloc( ( MaxSize + 1 ) * sizeof( T ) ); //把最前边的作为哨兵
if ( H == NULL )
Error( "out of space" );
//Heap初始化
H->Capacity = MaxSize;
H->Size = 0;
H->Elements[0] = Min; //这个Min是什么大家可以自己定义，比如INT_MIN
return H;
}
这个多一位的“哨兵”有2个好处，一个是左右孩子可以直接取2i和2i+1（不然的话第0位的2倍没有意义），第二个是在执行元素的插入操作时可以作为结束循环的判断。
那咱们就写一下如何Insert元素吧，因为堆是有顺序的，所以插入时必须要考虑如何把它放到合适的位置，一般，咱们先在堆的末端添加一个空位置，然后判断空位置放此元素是不是合理的，不合理的话就把此位置的父节点下移，然后尝试父节点的位置放置此元素是否合理，直到根节点：
template <typename T>
void insert( T x, PriorityQueue H )
{
int i;
if( Queue已经满了 )
{
Error;
return;
}
for( i = ++H->Size; H->Elements[i/2] > x; i /= 2) //i从一个新位置（size+1）开始
//这样在父节点的移动时就可以避免繁琐的swap例程，只用依次放入；而循环条件也很简单，
//只要父元素大于它，就把父元素下移，继续寻找父元素
H->Elements[i] = H->Elements[i/2];
H->Elements[i] = x;
}
我觉得我已经在code里把操作叙述的很清楚了，这里就不再多说，不过只说一点（还是要说啊），这个循环条件语句可以用简单的大小判断，就是因为我们把0位置设为了哨兵（一个很小的值），这样即使我们需要插入的值是最小值，当它插入到根节点的位置后，就必然大于0位置的值（1/2=0），从而结束循环。
有插入就有删除，我们实现一种删除，就是删除最小的元素：堆顶元素。其他的删除可以参考它：
template<typename T>
T DeleteTop( PriorityQueue H )
{
int i, int child;
T minElement, lastElement;
if( empty( H ) )
{
Error; //空
return H->Elements[0]; //返回第0个元素
}
minElement = H->Elements[1];
lastElement = H->Elements[H->Size--]; //赋给最后一个元素，同时size减1，因为要删除一个元素
for( i = 1; i * 2 <= H->Size; i = child)
//条件是(左)儿子在范围内，因为如果左孩子不在那么右孩子必然不在
{
child = i * 2;
if( child != H->size && H->elements[child + 1] < H->elements[child])
//这里我们没有明显检测右孩子是否存在，但是其实用了child != H->size来控制，这里的！=
//其实就是<，只有它不是最后一位，那么就保证了child+1位置的存在
child++;
if( lastElements>H->elements[child] )
H->elements[i] = H->elements[child];
else
break;
}
H->elements[i] = lastElements;
return minElements;
}
有了这个删除堆顶（最小）元素的例程，我们就可以做删除任意元素的操作：把想要删除的元素赋值为最小元素，即给它一个小于堆顶元素的值，然后Insert到堆顶，最后执行DeleteTop就好了。
我们写了很多关于二叉堆的操作，其实和马上要写的堆排序代码并不太一致，至少不需要掌握复杂的插入删除，但它是我们理解堆排序的必要知识。
现在我们来看堆排序就很简单了，它的主要操作就是：
- 拿数据建堆。
- 按照规则删堆（解散堆），因为只删除堆顶的，故最后得到的是一个有序序列。
假设我们还是需求一个非减序列，那么相应的，我们最好建一个最大堆，因为最大堆的top delete之后可以放到堆尾，这样的排序不需要额外的空间，可以说是相当成功了。
作为一个可以用的排序，我觉得应该从数组的第0位开始（废话，就这么一个数组做原地排序，你不从第0位开始从哪开始啊？），也因为是从第0位开始的，左孩子就不能是2i了（上边讲过），得是2i+1。那么，我们写写？
#define LeftChild(i) (2*(i)+1)
template<typename T>
void heap( T a[], int i, int n )
{
int child;
T tmp;
for( tmp = a[i]; LeftChild(i) < n; i = child )
{
child = LeftChild(i);
if( child != n - 1 && a[child+1] > a[child] )
child++;
if( tmp < a[child] ) //建立最大堆，那么就是parent小于child时，child上移
a[i] = a[child];
else
break; //找到了合适的位置，停止循环
}
a[i] = tmp;
}
这个建堆的基础操作，被我们拿来既用作建堆，也用做删堆，当然在这里更好的称呼是排序：建堆就不用讲了，就是从最后一位元素开始逐渐建立小堆，然后合并成大堆；而排序的过程就是把top元素放入堆尾，对其他元素做重建堆：
template<typename T>
void HeapSort( T a[], int n )
{
int i;
for( i = n/2; i >= 0; i-- )
heap( a, i, n ); //建堆
for( i = n - 1; i > 0; i--) //一个微小的点：i>0，不需要=，因为最后一项不用排序
{
swap( a[0], a[i] ); //交换第0项和最后一项后，排除最后一项建堆
heap( a, 0, i );
}
}
以上2段代码只有2个需要注意的地方，一是HeapSort()建堆的过程中，从i=n/2;开始，而不是很多代码的i=n-1;，因为最后一层并没有什么可建的，完全是浪费时间；二是在HeapSort()执行heap()时，最后一个参数是数组的数量，也就是数组的最后一项加1，因为在heap()中的循环条件决定了我们是拿n来比较的，这和其他排序的例程中使用n-1稍微有所区别。
目前，我们已经把所有经典的排序都过了一遍，顺便还讲了递归式的证明，以及二叉堆，在一般的算法课上，这大概需要不到一个月的时间，希望大家喜欢。
网友评论