堆排序

引论

堆我们很熟悉，它有个很好的性质：

树的最小值在根节点上，对于子树依旧成立

因此堆排序的思想也就明确了：

把数据以堆的方式存储，然后依次输出根节点。这样就可以把数据按照从小到大的顺序排列出来了。如果需要从大到小排列，则只需要在构建堆的时候，使树的根节点为最大值就可以了。

由堆的性质我们可以得出，堆排序的时间复杂度为$O（NlogN）$。

堆排序

由引论知道，我们只需要构建一个堆，然后依次输出根节点就好了，那么在这里还有什么可说的呢？

如果按照上面的思想，那么我们首先要建立一个堆，那么就需要一些额外的存储空间来存储这些输出的最小值，这样会增加算法的空间复杂度，因此这里介绍一种巧妙的算法来规避这一问题。

当我们对一个堆进行输出最小操作的时候，其实用于存放堆的数组就会空出一个空间，因此我们可以利用这个空间，把输出的排序好的数据一次存放在空出的空间中，如下如所示。

如果是按照从大到小排序的话，那么我们应该构建一个根节点为最大值的堆。

# define LeftChild(i) (2*(i)+1)
 
void PercDown(ElementType A[],int i,int N)
{
	int Child;
	ElementType 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])
			A[i] = A[Child];
		else
			break;
	}
	A[i] = Tmp;
}

void HeapSort(ElementType A[],int N)
{
	int i;
	for(i=N/2;i>=0;i--)
		PercDown(A,i,N);  //Build Heap
	for(i=N-1;i>0;i--)
	{
		Swap(&A[0],&A[i]);//swap the max-data to the last
		PercDown(A,0,i); //Build Heap for the remine data
	}
}

总结

建堆的过程，实际上就是一个排序的过程。