这里是指一种数据结构，而不是我们在C#中提到的用于存储引用类型对象的地方。它可以被当成一棵完全二叉树。一、基本概念
	

	堆：这里是指一种数据结构，而不是我们在C#中提到的用于存储引用类型对象的地方。它可以被当成一棵完全二叉树。

	 

	为了将堆用数组来存放，这里对每个节点标上顺序。事实上，我们可以用简单的计算公式得出父节点，左孩子，右孩子的索引：

	

		    parent(i) = 
	

		    left(i) = 2i
	

		    right(i)=2i + 1
	

		

			最大堆和最小堆: 最大堆是指所有父节点的值都大于其孩子节点的堆，即满足以下公式：
		

			                      A[parent[i]]A[i](A是指存放该堆的数组)
		

			    最小堆相反。
		

			    最大堆和最小堆是堆排序的关键，可知最大堆的根节点是堆中最大的节点。因此只要我们构造出最大(小)堆，最大(小)的元素也就得到了，然后再对剩下的元素继续构造最大(小)堆，就可以取出第二大(小)的元素，依此类推，直到排序完成。
	
	二、构造最大(小)堆 

	我们已经得知构造最大(小)堆是堆排序的关键，下面就来看看如何构造最大堆。

	万事开头难，首先来看一种特殊的情形吧：堆的根节点的左子树和右子树都已经是最大堆了，然而根节点却比孩子节点小，当然，这个堆不满足最大堆的定义。为了⑩这个堆成为最大堆，我们可以按如下步骤操作：

	（1）将根节点与左右孩子中最大的交换

	（2）交换之后可能会面临左或右子树不是最大堆的问题，但由于整个左(右)子树一开始就是最大堆，问题又回到了最开始的状态，因此只要如此反复即可得到最大堆。

	对于上面的特殊堆已经找到了解决办法，但对于一般意义上的堆呢？

	我们可以选择自底向上来构造：叶子节点是特殊的最大堆，举个例子有叶子节点a,b,它们的父节点是p;a,b肯定已经是最大堆了，这是要保证a,b,p组成的子树是最大堆。这个堆很眼熟是不是？没错，它就是前面提到的特殊的堆。在a,b,p组成的子树变成最大堆后，我们又可以类似的使该子树，该子树的父节点，以及同胞子树（或节点）组成的新子树成为最大堆，如此类推，最终使堆变为最大堆。

	

	对于求解最小堆与此类似。

	三、实现

	完整代码:

	

		复制代码 代码如下:
	

		

		namespace HeapSort

		{

		using System;

		class Program

		{

		static int heapSize =0;

		static void Main(string[] args)

		{

		var heap = new[] { -1, 10, 5, 12, 77, 54, 7, 34, 23, 11 };//为了方便，索引0处不存放元素（或存放无用元素）

		heapSize = heap.Length - 1;

		BuildMaxHeap(heap);

		for (var i = heap.Length - 1; i >= 2; i--)

		{

		//1.每次在构建好最大堆后，将第一个元素和最后一个元素交换；

		//2.第一次以索引1到length-1出的元素组成新的堆，第二次1到length-2，直到剩下最后两个元素组成堆

		//3.每次新组成的堆除了根节点其他节点都能保持最大堆的特性，因此只要DoBuildMaxHeap(heap, 1)就可以得到新的最大堆

		Swap(heap, 1, i);

		heapSize--;

		MaxHeapfy(heap, 1);

		}

		foreach (var i in heap)

		Console.Write(i + " ");

		}

		static void BuildMaxHeap(int[] heap)

		{

		for (var i = (heap.Length - 1) / 2; i >= 1; i--)

		{

		MaxHeapfy(heap, i);

		}

		}

		static void MaxHeapfy(int[] heap, int index)

		{

		var largerItemIndex = index;

		var leftChildIndex = index << 1;

		var rightChildIndex = (index<<1) + 1;

		if (leftChildIndex <= heapSize && heap[leftChildIndex] > heap[index])

		{

		largerItemIndex = leftChildIndex;

		}

		if (rightChildIndex <= heapSize && heap[rightChildIndex] > heap[largerItemIndex])

		{

		largerItemIndex = rightChildIndex;

		}

		if( index != largerItemIndex)

		{

		Swap(heap, index, largerItemIndex);

		MaxHeapfy(heap, largerItemIndex);

		}

		}

		static void Swap(int[] heap, int index1, int index2)

		{

		var temp = heap[index1];

		heap[index1] = heap[index2];

		heap[index2] = temp;

		}

		}

		}
	

	

		1.MaxHeapfy:该方法的前提是index处节点的左右子树已经是最大堆，最终的目的是使以index处节点为根的堆成为最大堆
	

		2.BuildMaxHeap：该方法涉及一个事实：如果一个对含n个元素，那么从开始的元素（假设节点下表从1开始）就一定是叶子节点（这一点可以用反证法证明，假设处节点不是叶子节点，那么该节点必包含子节点，从而可以得出其左孩子的索引2 *() > n的结论，显然这是错误的）。在这个前提下，该方法至底向上通过MaxHeapfy将堆构建成最大堆。