堆排序，首先要了解一下这里的堆是什么，这里的堆其实就是二叉树，很形象是不是，完整的二叉树从头看起，就是一个三角形，也可以看成一个“堆”。

一、数组转换成堆

        那么首先要解决的问题就是给数组排序，如何转换成二叉树的？转换方法如图：

数组 int a[]，包含元素a[0]，a[1]，a[2]，a[3].....等等。

转换成二叉树：

        图还是比较形象的，其实就是依次从堆顶向下排，但是有一个原则，就是上一层没有排满的时候，下一层不会有元素，有限排满上一层，才考虑下一层。

二、如何进行堆排序

那么第二个问题来了，我们怎么才能对其进行排序呢。

在考虑这个问题之前，我们需要先进行一些前序工作：

1、已知一个堆中的元素a[i]，它的父节点是谁？左右子节点呢(如果有)？

        通过观察不难得出，如果像我们上图这样，数组序号从0开始排起的话，元素a[i]的父节点(当然i不等于0时)是a[(i+1)/2 - 1]，而左右子节点分别是a[2*i+1]和a[2*i+2]；

2、引入大根堆的概念。

        大根堆：除根节点以外的所有及诶单a[i]都要满足：a[PARENT(i)]>=a[i]，这里parent(i)表示i的父节点的下标值；显然如果我们将一个树变成了一个大根堆，我们就可以得到一个当前树的最大值，也就是这个堆的顶部节点的值，由大根堆的性质可知。

3、对于一个左右子树已经是大根堆的根节点，怎样将以该节点为根的二叉树转换成大根堆？

        显然，如果根节点比左右子节点要大，那么已经是大根堆

        如果根节点比左右子节点要小，或者比其中一个要小？我们就需要将最大的那个子节点与根节点交换位置；但是这还没有完，因为原根节点交换到它的直接子节点位置之后，还不一定会满足大根堆的条件限制，如果不满足，我们就需要继续刚才的工作；

看看下面的代码：

/**
 * 在左右子树都是大根堆的情况下，形成新的大根堆
 */
void maxHeapIndex(int a[], int root, int maxSize) {
	//得到左子节点的下标
	int l = leftChildIndex(root);
	//得到右子节点的下标
	int r = rightChildIndex(root);
	//先默认最大节点的下标值为当前根节点
	int largest = root;

	//如果左节点存在且左节点的值大于根节点，则标记最大值为左节点
	if (l <= maxSize && a[l] > a[root]) {
		largest = l;
	}

	//如果左节点存在且右节点的值大于根节点，则标记最大值为右节点
	if (r <= maxSize && a[r] > a[largest]) {
		largest = r;
	}

	//经过标记判断，如果发现最大值确实不是根节点，则进行交换值，且进行递归调用看看交换之后的根节点是否满足大根堆性质
	if (root != largest) {
		swap(a + root, a + largest);
		maxHeapIndex(a, largest, maxSize);
	}
}

/*
 * 交换
 */
void swap(int* a, int* b) {
	int tmp = *a;
	*a = *b;
	*b = tmp;
}
/*
 * 得到左子节点的下标
 */
int leftChildIndex(int i) {
	return (i + 1) * 2 - 1;
}

/*
 * 得到右子节点的下标
 */
int rightChildIndex(int i) {
	return (i + 1) * 2;
}

4、堆中节点的下标关系。

        经过第3点，已经搞定了在左右子树都是大根堆的情况下，形成一个新的大根堆；那么我们如何让一颗没有处理过的堆来形成一个大根堆呢？如何找到左右子树都是大根堆的情况呢？找不到，那么不如先不要左右子树，那就是叶子节点，叶子节点没有左右子树，换言之它们就是天然的单节点大根堆；所以叶子节点的父节点都是满足3所假设的条件的，那么对于一个堆而言，叶子节点的父节点的下标的范围是多少呢？

        对于一个满节点二叉树而言，如果有h层，比如上图中到a[15]处，有三层；对于h层的满节点二叉树，它的节点个数是2*2^h-1，2^h即2的h次幂，叶子节点的个数为2^h，而除叶子节点之外的其他节点的个数为2^h-1个。我们不难得出，如果数组下标从0开始算起的话，除叶子节点以外的其他节点的下标范围应该是[0,2^h-2]。

        所以我们只需要从2^h-2位置的节点开始，也就是倒数第二层的最右边的节点开始。而对于高为h层，节点数为n的堆而言，h和n有如下关系：h=不小于lgn的最接近的整数；知道了上面这些，我们就可以从2^h-2位置开始一直到0位置一直循环执行第3点来实现形成一个大根堆：

/**
 * 生成一个大根堆，思路：
 * 从倒数第二层的最右边的节点开始，依次调用maxHeapIndex
 *
 */
void maxHeapBuild(int a[], int len) {
	//得到高度
	int h = log2(len);

	//得到可用的最大的下标值
	int max = (int) (pow(2, h)) - 2;

	//循环调用
	for (int i = max; i >= 0; i--) {
		maxHeapIndex(a, i, len - 1);
	}
}

/**
 * 得到log2为底的值
 */
int log2(int i) {
	//ceil函数返回一个不小于某值的整数
	return (int) ceil(log(i) / log(2));
}

三、堆排序过程

        经过上面四步，我们已经可以得到一个大根堆了，接下来的工作就是如何利用大根堆来进行排序。

        对于大根堆而言，我们唯一可以确定的是，它的顶部的那个元素一定是当前堆中最大的元素，于是我们可以每次将顶部的元素和最右边的叶子节点也就是最后一个叶子节点进行交换，然后拿出这个最大值，并且将堆的节点数减一，然后重新对顶点也就是刚才那个交换到顶点位置的叶子节点进行上面3、中的操作，来重新让新堆变成一个大根堆，然后我们依次循环执行上面的操作，直到取出堆中的所有元素，这样，我们从开始到最后取出的元素是按照从大到小的顺序，也就完成了排序。

这一步的代码很简单：

/*
 * 堆排序，思路：
 * 先进行一次maxHeapBuild，使得root节点为最大的值
 * 然后将root节点和最后一个节点的值进行交换
 * 然后将最后一个节点断开（maxsize-=1）
 * 然后进行maxheapify，因为这时候根节点的左右子树依旧是大根堆，所以只需要maxheapify而不需要maxHeapBuild
 * 这样从n-1开始循环到2的时候即可
 */

void maxHeapSort(int a[], int maxSize, int tmp[]) {
	maxHeapBuild(a, maxSize); //n

	for (int i = maxSize; i > 0;) { //循环n-1次
		swap(a, a + i);
		tmp[i] = a[i];
		i--;

		if (i == 0) {
			tmp[0] = a[0];
		} else {
			maxHeapIndex(a, 0, i); //logn 执行了n-2次
		}
	}

	for (int i = 0; i <= maxSize; i++) {
		a[i] = tmp[i];
	}
}

四、堆排序时间复杂度

        对于堆排序算法，我们简单的看一下它的时间复杂度，一次maxHeapBuild的时间复杂度是n，然后循环n-1的maxHeapIndex时间复杂度为nlogn，循环赋值操作复杂度为n，所以算起来，时间复杂度为nlogn。

算法基础之五(堆排序)