一、实现思路
堆排序因其巧妙的利用堆这种数据结构的特性来进行排序而得名。要了解其实现原理需要先了解堆这种数据结构。
堆是一种特殊的二叉树数据结构。有两种类型的堆：大顶堆与小顶堆。其具有任意的根节点均大于等于其子节点（大顶堆）或小于等于其子节点（小顶堆）的性质。同时也具有完全二叉树的性质。
堆具有二叉树与数组两种表现形式，如下图所示：
堆结构还可以用来实现优先级队列，优先级队列在很多场合都有应用，如A*算法中用于优化开放节点的查找速度，操作系统中任务优先调度算法等等。
堆排序就是利用堆(假设利用大顶堆)进行排序的方法。它的基本思想是，将待排序的序列构造成一个大顶堆。此时，整个序列的最大值就是堆顶的根结点。将它移走(其实就是将其与堆数组的末尾元素交换，此时末尾元素就是最大值)，然后将剩余的n-1个序列重新构造成一个堆，这样就会得到n个元素中的次小值。如此反复执行，便能得到一个有序序列了。
二、代码实现
public class Heap
{
public enum HeapType
{
SmallHeap,
BigHeap
}
//堆节点从1开始存储，这是为了方便计算其索引
int[] nodes;//节点容器
public int Capacity { get; set; }//容量
public int Count { get; private set; }//记录总数
public HeapType heapType { get; }//堆属性
public Heap(int capacity, HeapType type = HeapType.SmallHeap)
{
Capacity = capacity;
nodes = new int[capacity + 1];
heapType = type;
}
//压入节点返回压入成功结果
public bool PushNode(int node)
{
if (Count >= Capacity)
{
return false;
}
nodes[++Count] = node;
UpFilter(Count);
return true;
}
//弹出节点
public int PopNode()
{
if (Count <= 0)
{
throw new System.Exception("堆下溢");
}
int value = nodes[1];
nodes[1] = nodes[Count--];
DownFilter(1);
return value;
}
public void Clear()
{
Count = 0;
}
//堆排序
public void Sort(int[] arr)
{
Clear();
//构建堆
foreach (var item in arr)
{
PushNode(item);
}
int index = 0;
while (Count>0)
{
arr[index++] = PopNode();
}
}
//向上过滤
void UpFilter(int index)
{
if (index == 1)
{
return;
}
if (heapType == HeapType.SmallHeap)
{
//小跟堆
if (nodes[index] < nodes[index / 2])
{
//执行交换
SwapNode(index / 2, index);
UpFilter(index / 2);//递归调用
}
}
else
{
//大根堆
if (nodes[index] > nodes[index / 2])
{
//执行交换
SwapNode(index / 2, index);
UpFilter(index / 2);//递归调用
}
}
}
//向下过滤
void DownFilter(int index)
{
//没有子节点退出
if (index * 2 > Count)
{
return;
}
if (heapType == HeapType.SmallHeap)
{
//取当前节点与其左右子节点决出最小节点
int minIndex = nodes[index] > nodes[index * 2] ? index * 2 : index;
if (index * 2 + 1 <= Count)
{
minIndex = nodes[minIndex] > nodes[index * 2 + 1] ? index * 2 + 1 : minIndex;
}
if (nodes[index].Equals(nodes[minIndex]))
{
//最小的是自身则返回
return;
}
else
{
//交换节点
SwapNode(minIndex, index);
DownFilter(minIndex);
}
}
else
{
//取当前节点与其左右子节点决出最大节点
int maxIndex = nodes[index] < nodes[index * 2] ? index * 2 : index;
if (index * 2 + 1 <= Count)
{
maxIndex = nodes[maxIndex] < nodes[index * 2 + 1] ? index * 2 + 1 : maxIndex;
}
if (nodes[index].Equals(nodes[maxIndex]))
{
//最大的是自身则返回
return;
}
else
{
//交换节点
SwapNode(maxIndex, index);
DownFilter(maxIndex);
}
}
}
//交换两个节点
void SwapNode(int index1, int index2)
{
//执行交换
int temp = nodes[index1];
nodes[index1] = nodes[index2];
nodes[index2] = temp;
}
}
public static void HeapSortNormal(int[] arr)
{
//构建堆
Heap heap = new Heap(arr.Length);
heap.Sort(arr);
}
上述代码实现了一个堆数据结构，提供了容量、堆类型设置，以及push、pop、sort等基本操作。
堆实现的核心在于上浮与下沉两个操作。通过这两个方法来维护堆的性质不被破坏。弹出一个节点时会将堆的最后一个节点插入到根节点，这样可以不破坏中部的结构，再通过下沉操作将该节点下沉到合适的位置，下图演示了下沉操作是如何进行的：
而上浮操作则于之相反。在插入一个节点时，将其插入到堆的末尾，再通过上浮操作浮动到适当位置。
在实现了push与pop操作后，便可以简单的利用这两个操作的组合来实现sort操作。
当然我们只想利用堆结构来完成排序，并不需要它其他的功能，实现一个完整的堆结构是没有必要的，并且上述的这种实现，由于存储了待排序数组的副本需要额外的空间，并且其在构建堆时采用了自上而下的构建方式。这样每插入一个新的节点都要从根节点开始下沉，其复杂度受到树深的影响。因此便有了下面的优化实现：
public static void HeapSort(int[] arr)
{
//初始化构建堆
BuildHeap(arr);
//始终将0号位置元素交换到末尾，使末尾有序，并缩减heap尺寸
for (int size = arr.Length; size > 0; size--)
{
//将第一个元素（最大的元素）与heap末尾元素交换，对应数组索引为size-1
Swap(arr, 0, size - 1);
//交换后heap实际尺寸变为size-1，重建堆
DownFilter(arr, size - 1, 0);
}
//自下而上构建堆
void BuildHeap(int[] arr)
{
for (int i = arr.Length/2-1; i >= 0; i--)
{
DownFilter(arr,arr.Length,i);
}
}
//下沉
void DownFilter(int[] arr,int heapSize,int index)
{
//计算子节点索引
int left = (index + 1) * 2 - 1;
int right = left+1 ;
//目标位置
int target = index;
//如果存在左孩子且比目标节点大则目标下沉
if (left + 1 <= heapSize && arr[left] > arr[target]) target = left;
//如果存在右孩子且比目标节点大则目标下沉
if (right + 1 <= heapSize && arr[right] > arr[target]) target = right;
//如果最大的是目标节点本身则跳出递归
if (target==index)
{
return;
}
//节点交换，下沉目标节点
Swap(arr,index,target);
//递归调用
DownFilter(arr,heapSize,target);
}
}
这个实现中，整个排序过程，包括堆的构建与排序等全部都在原址进行，因此其空间复杂度为常量级。并且其采用了自下而上的方法初始化堆的构建，这种方法的思路是从最后一个不为叶子的节点开始依次往前进行下沉操作，因此每个节点仅需一次调整即可，相比上面的简单实现，建堆的过程的时间复杂度从O(nlogn)下降到了O(n)。其构建过程如下所示：
整个算法的运行过程图示如下：
三、复杂度分析
堆排序运行时间主要是消耗在初始构建堆和在重建堆时的反复筛选上。
对于自下而上的构建堆过程由于只进行必要的交换因此其复杂度为O(n)，在正式排序时，第1次取堆顶记录重建堆需要用O(logi)的时间,并且需要取n-1次堆顶记录，因此，重建堆的时间复杂度为O(nlogn)。
所以总体来说，堆排序的时间复杂度为O(nlogn)。由于堆排序对原始记录的排序
状态并不敏感，因此它无论是最好、最坏和平均时间复杂度均为O(nlogn)。
空间复杂度上，它只有一个用来交换的暂存单元，也非常的不错。
另外，由于初始构建堆所需的比较次数较多，因此，它并不适合待排序序列个数较少的情况。
总结
堆排序实际可以看作选择排序的一种改进实现，它通过在选择到最小的数时对其他记录进行调整，从而避免了冗余的比较来提高获取下一次选择效率。其在时间空间复杂度上都有不错的表现。