Go语言堆排序详解（从零开始掌握堆化操作与堆排序算法）

堆化操作（Heapify）是什么？

堆化操作是指将一个普通数组（或子树）调整为满足堆性质的过程。在堆排序中，我们从最后一个非叶子节点开始，自底向上进行堆化，确保整棵树满足最大堆的性质。

关键点：对于索引为 i 的节点，其左子节点索引为 2*i + 1，右子节点索引为 2*i + 2，父节点索引为 (i-1)/2。

Go语言实现堆化操作

下面是一个完整的 Go语言堆排序 实现，包含堆化函数和主排序逻辑：

package mainimport "fmt"// heapify 函数：将以 index 为根的子树调整为最大堆func heapify(arr []int, n int, i int) {    largest := i          // 初始化最大值为根    left := 2*i + 1       // 左子节点    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] = arr[largest], arr[i]        heapify(arr, n, largest) // 递归堆化受影响的子树    }}// heapSort 函数：执行堆排序func heapSort(arr []int) {    n := len(arr)    // 第一步：构建最大堆（从最后一个非叶子节点开始）    for i := n/2 - 1; i >= 0; i-- {        heapify(arr, n, i)    }    // 第二步：逐个提取堆顶元素（最大值），放到数组末尾    for i := n - 1; i > 0; i-- {        arr[0], arr[i] = arr[i], arr[0] // 将最大值移到末尾        heapify(arr, i, 0)              // 对剩余元素重新堆化    }}func main() {    data := []int{12, 11, 13, 5, 6, 7}    fmt.Println("原始数组:", data)    heapSort(data)    fmt.Println("排序后数组:", data)}

代码解析

• heapify 函数负责维护堆的性质。它比较当前节点与其左右子节点，若子节点更大，则交换并递归处理被影响的子树。
• heapSort 函数分两步：
    1. 构建初始最大堆（从 n/2 - 1 开始，因为这是最后一个非叶子节点）；
    2. 重复取出堆顶（最大值），缩小堆范围，并重新堆化。

为什么堆排序高效？

堆排序的时间复杂度为 O(n log n)，空间复杂度为 O(1)（原地排序）。它不像快速排序那样受输入数据影响，性能稳定，非常适合需要确定性时间复杂度的场景。

总结

通过本教程，你已经掌握了 Go语言堆排序 的核心——堆化操作。无论是面试还是实际开发，理解堆的结构和堆排序的实现都非常重要。建议你动手运行上面的代码，修改数组内容，观察排序过程，加深理解。

关键词回顾：Go语言堆排序、堆化操作、堆排序算法、Go实现堆排序。