C#堆排序详解（从零开始掌握堆结构构建与排序实现）

为什么用数组表示堆？

虽然堆是树形结构，但在实际编程中，我们常用数组来存储堆，因为完全二叉树具有良好的索引规律：

• 对于索引为 i 的节点：
• 左子节点索引 = 2 * i + 1
• 右子节点索引 = 2 * i + 2
• 父节点索引 = (i - 1) / 2

堆结构构建的核心：Heapify 方法

构建堆的关键在于 Heapify 方法——它能确保以某个节点为根的子树满足堆的性质。

以下是 C# 中实现最大堆的 Heapify 方法：

private static void Heapify(int[] arr, int n, int i){    int largest = i;           // 假设当前节点 i 是最大值    int left = 2 * i + 1;      // 左子节点索引    int right = 2 * i + 2;     // 右子节点索引    // 如果左子节点存在且大于当前最大值    if (left < n && arr[left] > arr[largest])        largest = left;    // 如果右子节点存在且大于当前最大值    if (right < n && arr[right] > arr[largest])        largest = right;    // 如果最大值不是当前节点，则交换并继续调整    if (largest != i)    {        // 交换 arr[i] 和 arr[largest]        int temp = arr[i];        arr[i] = arr[largest];        arr[largest] = temp;        // 递归调用 Heapify，确保子树仍满足堆性质        Heapify(arr, n, largest);    }}

完整构建堆的步骤

要将一个无序数组构建成最大堆，我们需要从最后一个非叶子节点开始，自底向上调用 Heapify。

最后一个非叶子节点的索引为 (n / 2) - 1（n 为数组长度）。

public static void BuildMaxHeap(int[] arr){    int n = arr.Length;    // 从最后一个非叶子节点开始，向前遍历    for (int i = n / 2 - 1; i >= 0; i--)    {        Heapify(arr, n, i);    }}

完整示例：构建堆并打印结果

using System;class Program{    static void Main()    {        int[] arr = { 4, 10, 3, 5, 1 };        Console.WriteLine("原始数组: " + string.Join(", ", arr));        BuildMaxHeap(arr);        Console.WriteLine("构建最大堆后: " + string.Join(", ", arr));        // 输出：10, 5, 3, 4, 1    }    private static void Heapify(int[] arr, int n, int i)    {        // ...（如上所示）    }    public static void BuildMaxHeap(int[] arr)    {        // ...（如上所示）    }}

总结

通过本教程，你已经掌握了 C#堆排序 中最核心的部分——堆结构构建。理解 Heapify 和 BuildMaxHeap 是实现完整堆排序算法的第一步。接下来，你只需在堆顶取出最大值、缩小堆大小、重新调整堆，即可完成排序。

希望这篇 C#算法教程 能帮助你轻松入门堆排序！如果你正在学习数据结构或准备面试，掌握 堆排序实现 将为你打下坚实基础。

关键词回顾：C#堆排序、堆结构构建、C#算法教程、堆排序实现