堆排序

堆排序是利用一种叫堆的数据结构进行排序的算法，时间复杂度为O(nlogn)，空间复杂度为O(1)。

什么是堆？堆分为最大堆和最小堆。堆首先是一颗完全二叉树，最大堆满足父节点的值大于等于它的所有子节点的值，最小堆就不用多说了。

下面我只说利用最大堆对数组进行升序排序的情况。

堆排序中有一个很重要的函数，void maxHeadify(T *A, int i)。这个函数的前提是节点i的左右子树都已经是最大堆了，这个函数让使以节点i为根节点的数为最大堆。实现方法很简单，首先找到节点i以及它的两个子节点中最大的那个，然后把它和节点i交换，然后再对它递归调用函数maxHeadify。

排序时，首先构建最大堆。即把输入的数组A转化为最大堆。因为完全二叉树从第n/2+1—n都是叶子节点，而叶子节点可以看做是只包含一个元素的堆，这样就可以从后往前调用maxHeadify，这样就可以构建好最大堆。然后将数组的第一个元素与最后的元素交换，那么最大的那个数就已经到了它正确的位置上了。接着把最后的那个元素排除在最大堆之外，即最大堆的长度-1。然后调用maxHeadify(A, 0)，再次使堆最大化。这样重复调用n-1次，排序就完成了。

下面是具体的实现：

#include <iostream>
#include <algorithm>

/*
**使以i为根的子树保持最大堆的性质
**此函数的前提是以i的左儿子和右儿子为根的子树都是最大堆
**n为数组元素个数
*/
template <typename T>
void maxHeadify(T* A, int n, int i)
{
	int leftChild = (i << 1) + 1;
	int rightChild = (i << 1) + 2;
	int largest = i;

	/* 从A[i]、A[leftChild]、A[rightChild]中找出最大值，下标保存在largest中 */
	if(leftChild < n && A[leftChild] > A[largest])
		largest = leftChild;
	if(rightChild < n && A[rightChild] > A[largest])
		largest = rightChild;

	if(largest != i)
	{
		std::swap(A[largest], A[i]);	//将最大值交换到根节点
		maxHeadify(A, n, largest);		//递归调用，使largest保持最大堆
	}
}

template <typename T>
void heapSort(T* A, int n)
{
	//自底向上构建最大堆
	for(int i = (n - 1) / 2; i >= 0; --i)
		maxHeadify(A, n, i);

	//依次把根节点移动到数组的最后
	for(int i = n - 1; i >= 1; --i)
	{
		std::swap(A[i], A[0]);
		maxHeadify(A, i, 0);
	}
}


int main()
{
	int A[] = {4, 1, 3, 2, 16, 9, 10, 14, 8, 7};
	heapSort(A, 10);

	return 0;
}