堆排序

堆排序的核心就是如何建堆以及如何保持堆的性质，而建堆也是利用保持堆的性质来实现的，因此最核心的就是如何保持堆的性质，以大根堆为例说明:

大根堆必须满足如下性质：

1.每个结点的值都不小于它的左右子树根节点的值  

2.是一个完全二叉树

首先来看，如何保持大根堆的性质？

我们使用 MaxHeapify (int array[], int length, int root)函数来实现，关键思想是：在调用本函数之前，假设以root的子女left[root] 和 right[root] 为根的子树都是大根堆，但是array[root] 可能小于它的子女，这就违背了大根堆的性质，因此找出array[root]  、左右子女3个元素中最大的一个与array[root] 交换，但是交换之后就破坏了原有的左右子树的大根堆，因此递归调用 MaxHeapify 继续保持大根堆的性质，代码如下：

/*
* 函数介绍：用来保持大根堆的性质
* 输入参数：数组指针、数组长度
            root为数组下标，从0开始计算
* 输出参数：无
* 返回值  ：空
*/
void MaxHeapify (int array[], int length, int root)
{
	int left = 2*root + 1;
	int right = 2*root + 2;
	int largest = root;
	
	if ( (left < length) && (array[left] > array[largest]) )
	{
		largest = left;
	}

	if( (right < length) && (array[right] > array[largest]) )
	{
		largest = right;
	}

	if( largest != root )
	{
		int temp = array[root];
		array[root] = array[largest];
		array[largest] = temp;
		MaxHeapify(array, length, largest);
	}	
}

利用上述函数就可以自底向上完成建堆的工作，因为完全二叉树的所有叶子节点本身就是大根堆，因此只需要从最靠后的非叶子节点开始，针对每一个结点调用MaxHeapify，这样就完成了建堆的工作。代码如下：

void BuildMaxheap(int array[], int length)
{
	for( int i = length/2 ; i > 0; --i)
		MaxHeapify(array, length, i-1);
	
}

然后，就可以利用上述函数进行堆排序了。因为大根堆的根就是最大的元素，所以考虑将根与最后的叶子节点交换，但是交换破坏了大根堆，因此需要调用MaxHeapify来保持大根堆的性质，然后再将次大的元素与倒数第二个叶子节点交换，如此反复，就可以得到一个有序序列。代码如下：

/*
* 函数介绍：首先建立大根堆，然后将数组第一个元素（最大元素）与数组最后一个元素交换，
*           并递减数组长度，调用MaxHeapif保持大根堆的性质 
* 输入参数：数组和数组长度
* 输出参数：无
* 返回值  ：排好序的数组指针
*/
int *HeapSort(int array[], int length)
{
	BuildMaxheap(array, length);
	for(int i = length ; i > 1; --i)
	{
		int temp = array[length-1];
		array[length-1] = array[0];
		array[0] = temp;
		--length;
		MaxHeapify(array, length, 0);
	}
	return array;
}

注：《算法导论》中所说的数组下标是从1开始算的，所以实现的时候要适当调整，并注意边界条件。

堆排序,布布扣,bubuko.com

堆排序

原文：http://blog.csdn.net/xinshen1860/article/details/21345249