堆排序

堆排序与快速排序，归并排序一样都是时间复杂度为O(N*logN)的几种常见排序方法。

先说说什么是堆，堆通常是一个可以被看做一棵树的数组对象。满足下列性质：

1.堆中某个节点的值总是不大于或不小于其父节点的值；

2.堆总是一棵完全树（完全树就是叶结点仅在层次最大的两层出现的树）。

将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。由于其它几种堆（二项式堆，斐波纳契堆等）用的较少，一般将二叉堆就简称为堆。

堆的存储

一般都用数组来表示堆，i结点的父结点下标就为(i – 1) / 2。它的左右子结点下标分别为2 * i + 1和2 * i + 2。如第0个结点左右子结点下标分别为1和2。

堆的操作

建立堆：

一般情况下，树并不满足堆的条件，通过重新排列元素，可以建立一棵”堆化“的树。如初始表：55 12 16，堆化后为：12 55 16。

堆的插入：

每次插入都是将新数据放在数组最后。然后树被更新以恢复堆次序。如初始表：12 22 7 ，插入新数据后，数组为12 22 7 16，然后重排树的顺序，数组为12 16 7 22。

可以发现从这个新数据的父结点到根结点必然为一个有序的数列。

//  新加入i结点  其父结点为(i - 1) / 2
void MinHeapFixup(int a[], int i)
{
    int j, temp;
	
	temp = a[i];
	j = (i - 1) / 2;      //父结点
	while (j >= 0 && i != 0)
	{
		if (a[j] <= temp)
			break;
		
		a[i] = a[j];     //把较大的子结点往下移动,替换它的子结点
		i = j;
		j = (i - 1) / 2;
	}
	a[i] = temp;
}

//在最小堆中加入新的数据nNum
void MinHeapAddNumber(int a[], int n, int nNum)
{
	a[n] = nNum;
	MinHeapFixup(a, n);
}

堆中每次都只能删除第0个数据。为了便于重建堆，实际的操作是将最后一个数据的值赋给根结点，然后再从根结点开始进行一次从上向下的调整。调整时先在左右儿子结点中找最小的，如果父结点比这个最小的子结点还小说明不需要调整了，反之将父结点和它交换后再考虑后面的结点。相当于从根结点将一个数据的“下沉”过程。

如初始表：12 16 50 22，删除第0个数据后，数组为22 16 50 _，然后重排树的顺序，数组为16 22 50。

//  从i节点开始调整,n为节点总数 从0开始计算 i节点的子节点为 2*i+1, 2*i+2
void MinHeapFixdown(int a[], int i, int n)
{
    int j, temp;

	temp = a[i];
	j = 2 * i + 1;
	while (j < n)
	{
		if (j + 1 < n && a[j + 1] < a[j]) //在左右孩子中找最小的
			j++;

		if (a[j] >= temp)
			break;

		a[i] = a[j];     //把较小的子结点往上移动,替换它的父结点
		i = j;
		j = 2 * i + 1;
	}
	a[i] = temp;
}
//在最小堆中删除数
void MinHeapDeleteNumber(int a[], int n)
{
	Swap(a[0], a[n - 1]);
	MinHeapFixdown(a, 0, n - 1);
}

堆排序

原文：http://blog.csdn.net/losophy/article/details/19704639