Go 数据结构之堆排序示例详解

什么是堆？

堆（Heap）是一种特殊的树形数据结构，它满足下列性质：

1. 堆中每个节点的关键字都不大于（或不小于）其子节点的关键字。
2. 堆中，根节点（顶端）是最小或最大元素。

堆实际上是一个完全二叉树，因此可以用数组实现。对于下标为i的节点，其左子节点为2i，右子节点为2i+1，父节点为i/2。

堆分为最大堆和最小堆。在最大堆中，父节点的值大于子节点的值；在最小堆中，父节点的值小于子节点的值。

堆的时间复杂度为O(logN)。

堆排序的过程

堆排序是利用堆进行排序的方法。排序过程分为两个步骤：建立堆和排序。

建立堆

建立堆的过程是将无序的数组构建成一个堆。这个过程可以使用自下而上的方法从最后一个节点开始构建，由于堆中不存在孙子节点，因此可以忽略孙子节点的排列。

示例一：

func buildHeap(arr []int) {
    n := len(arr)
    for i := n / 2 - 1; i >= 0; i-- {
        heapify(arr, n, i)
    }
}

func heapify(arr []int, n, i int) {
    max := i     // 找到父节点、左节点、右节点中的最大值
    l, r := 2*i+1, 2*i+2
    if l < n && arr[l] > arr[max] {
        max = l
    }
    if r < n && arr[r] > arr[max] {
        max = r
    }
    if max != i {   // 如果最大值不是父节点，则交换父节点和最大值
        arr[i], arr[max] = arr[max], arr[i]
        heapify(arr, n, max)    // 递归地对最大值所在的子树进行堆化
    }
}

在上面的代码中，buildHeap()函数从最后一个节点的父节点开始进行堆化，调用heapify()函数进行堆化。

heapify()函数用于将一个节点及其子树堆化。首先找到父节点、左节点、右节点中的最大值，如果最大值不是父节点，则交换父节点和最大值，并递归地对被交换的子节点进行堆化。

排序

建立好堆之后，进行排序的过程就是将堆顶元素（最小或最大值）与数组的最后一个元素交换，然后将堆的大小减1，并对新的堆顶进行堆化。重复这个过程直到堆的大小为1。

示例二：

func heapSort(arr []int) {
    n := len(arr)
    buildHeap(arr)  // 先建立堆
    for i := n - 1; i > 0; i-- {
        arr[0], arr[i] = arr[i], arr[0]     // 将堆顶元素（最小值）与最后一个元素交换
        heapify(arr, i, 0)  // 对新的堆顶进行堆化
    }
}

在上面的代码中，heapSort()函数在建立好堆之后，对堆进行排序，在每一次循环中，将堆顶元素与数组的最后一个元素交换，并对新的堆顶进行堆化。

总结

堆排序是一种简单、高效的排序算法。它利用了堆的特点，建立和操作起来都比较容易。在建立堆的过程中，可以选择自下而上的、或自上而下的方法进行堆化。在排序过程中，每次将堆顶元素（最小或最大值）与数组的最后一个元素进行交换，而不必临时占用额外的空间。由于堆的时间复杂度为O(logN)，因此堆排序的时间复杂度为O(NlogN)。