堆排序可以看作选择排序的一种优化版本。它不再通过线性扫描查找最大值，而是借助大顶堆的结构让最大值始终位于堆顶。C#中实现堆排序通常不需要构造真正的树节点对象，直接基于数组操作即可完成全部逻辑。数组下标与完全二叉树的节点位置存在固定的数学关系，这也是后续调整算法的基础。
对于下标从0开始的数组，某个节点i的左子节点下标为2*i+1，右子节点下标为2*i+2，父节点下标为(i-1)/2。这个公式是整个算法的基础，因为堆排序的所有调整都依赖它来定位元素。
一、堆调整：让任意子树恢复大顶堆性质
堆排序的全部核心都集中在一个调整函数上。这个函数的作用是：给定一个节点下标，假设它的左右子树已经满足堆性质，把当前节点向下移动到正确位置，使整棵子树满足父节点大于等于子节点的约束。该过程通常称为下滤或sift down。
C#中实现时使用递归比较直观，但需要明确递归终止条件。先计算当前节点、左孩子、右孩子三者中的最大下标，如果最大值不是当前节点，就交换并继续向下调整。这里递归深度最多为树高，也就是log n级别，因此一般不会出现栈溢出问题。唯一需要反复检查的是左右子节点下标是否小于堆的有效长度，漏掉这个判断会直接导致数组越界异常。
public static void MaxHeapify(int[] array, int heapSize, int rootIndex)
{
int largest = rootIndex;
int leftChild = 2 * rootIndex + 1;
int rightChild = 2 * rootIndex + 2;
if (leftChild < heapSize && array[leftChild] > array[largest])
{
largest = leftChild;
}
if (rightChild < heapSize && array[rightChild] > array[largest])
{
largest = rightChild;
}
if (largest != rootIndex)
{
int temp = array[rootIndex];
array[rootIndex] = array[largest];
array[largest] = temp;
MaxHeapify(array, heapSize, largest);
}
}
函数中的heapSize参数很关键。堆排序过程中，数组末尾已经排好的元素不再参与堆调整，所以有效堆长度会逐步减小。如果不传这个参数，而是固定使用数组总长度，已排序部分会被重新拉到堆顶，破坏排序结果。
实际调试时，可以试着用数组{4, 10, 3, 5, 1}手动执行一次调整。根节点4小于左孩子10，交换后10成为根节点，而4继续与左孩子5比较，又发生交换。最终10到达顶部，数组变成{10, 5, 3, 4, 1}。这个过程体现了下滤操作逐层下沉的特点。
二、构建大顶堆与排序主流程
有了调整函数之后，建堆并不需要从空堆开始逐个插入元素。更高效的做法是从最后一个非叶子节点开始，自下而上依次调用调整函数。最后一个非叶子节点的下标为array.Length / 2 - 1。这样做可以保证每一轮调整时，子树已经是大顶堆，符合调整函数的前置条件。
建堆完成后，数组的第一个元素一定是最大值。排序循环将堆顶元素与当前有效堆的最后一个元素交换，然后让堆长度减一，再对新的堆顶进行调整。每一轮都会把当前最大值放到数组末尾，循环结束后数组就变为升序。整个过程不需要额外数组，直接在原数组内部完成。
public static void BuildMaxHeap(int[] array)
{
for (int i = array.Length / 2 - 1; i >= 0; i--)
{
MaxHeapify(array, array.Length, i);
}
}
public static void HeapSort(int[] array)
{
BuildMaxHeap(array);
for (int i = array.Length - 1; i > 0; i--)
{
int temp = array[0];
array[0] = array[i];
array[i] = temp;
MaxHeapify(array, i, 0);
}
}
从代码可以看出，建堆阶段看起来是线性循环，但每次调整的复杂度是O(log n)，总体为O(n)级别，比逐个插入的O(n log n)更优。这一点经常被误认为建堆也是O(n log n)。严格推导可以得出建堆总代价为O(n)，不过排序阶段仍需要O(n log n)。
交换元素后数组后半部分逐步有序，而堆的规模不断缩小。注意循环变量i既表示当前堆的末尾位置，也代表本轮要放置最大值的位置。调整调用中第三个参数是i而不是数组长度，这是最容易写错的地方。
三、泛型实现与自定义比较规则
针对int数组的实现便于理解算法，但实际项目中经常需要对自定义类型排序。C#中可以借助泛型和Comparison<T>委托来提供比较规则。泛型版本不需要类型实现IComparable<T>，调用方可以传入lambda表达式指定排序字段。
泛型调整函数的结构与int版本完全一致，区别仅在于比较操作从>改为调用委托。使用comparison(array[leftChild], array[largest]) > 0表示左孩子大于当前最大值，对应升序排序。如果想要降序，可以在调用时反转比较结果，或者把判断条件中的大于改为小于。
public static void HeapSort<T>(T[] array, Comparison<T> comparison = null)
{
comparison = comparison ?? Comparer<T>.Default.Compare;
int heapSize = array.Length;
for (int i = heapSize / 2 - 1; i >= 0; i--)
{
Heapify(array, heapSize, i, comparison);
}
for (int i = array.Length - 1; i > 0; i--)
{
T temp = array[0];
array[0] = array[i];
array[i] = temp;
Heapify(array, i, 0, comparison);
}
}
private static void Heapify<T>(T[] array, int heapSize, int rootIndex, Comparison<T> comparison)
{
int largest = rootIndex;
int leftChild = 2 * rootIndex + 1;
int rightChild = 2 * rootIndex + 2;
if (leftChild < heapSize && comparison(array[leftChild], array[largest]) > 0)
{
largest = leftChild;
}
if (rightChild < heapSize && comparison(array[rightChild], array[largest]) > 0)
{
largest = rightChild;
}
if (largest != rootIndex)
{
T temp = array[rootIndex];
array[rootIndex] = array[largest];
array[largest] = temp;
Heapify(array, heapSize, largest, comparison);
}
}
这类泛型封装适合放进公共工具类中。调用示例可以写为HeapSort(students, (a, b) => a.Score.CompareTo(b.Score))。由于泛型方法在编译时会生成具体类型版本，性能与手写代码基本一致。需要注意的是，如果对象本身包含null值，比较委托应当提前处理空引用，否则会抛出异常。
还可以进一步将方法扩展为IList<T>接口版本，但数组已经能够覆盖大多数排序场景。保持参数为数组可以让代码更简单，也更贴近算法学习的核心目标。
四、稳定性、复杂度与快速排序的对比
堆排序的时间复杂度在最坏、平均和最好情况下都是O(n log n)，空间复杂度为O(1)。这一点使它在内存极度受限或需要保证最坏情况性能时具有一定优势。不过由于交换操作可能跨越大距离，堆排序是不稳定排序。相同值的元素在排序后相对顺序可能改变。
与快速排序相比，堆排序没有递归分区带来的栈空间消耗，也不会因为基准值选择不当而退化到O(n²)。但堆排序的常数因子通常更大，因为在调整过程中需要频繁跳跃访问数组元素，缓存局部性不如快速排序。实际基准测试中，快速排序在随机数据上往往更快，而堆排序更多用于需要硬性时间保证的场景。
如果数据量较小，直接使用插入排序可能更高效；如果数据量较大且要求稳定性，归并排序更合适。堆排序的核心价值在于原地排序与O(n log n)最坏情况时间复杂度的组合，理解它的调整过程也有助于掌握优先队列等数据结构。
最后需要注意，C#标准库中的Array.Sort对于基础类型使用快速排序或内省排序，并不采用堆排序。手动实现堆排序更多是算法学习和特定约束下的选择。掌握其数组索引计算和递归调整逻辑，能显著提升对树形结构的理解。