跳转至

堆排序

堆是具有以下性质的完全二叉树：

  1. 每个节点的值都大于或等于其左右孩子节点的值，称为大顶堆；
  2. 或者每个节点的值都小于或等于其左右孩子节点的值，称为小顶堆。
小顶堆
    10
   /     \
  20     15
 / \        / \
25 50 30 40 

大顶堆
    50
   /     \
  45     40
 / \        / \
20 25 35 30

我们对堆中的节点按层进行编号，将这种逻辑结构映射到数组中就是：[50, 45, 40, 20, 25, 35, 30]。该数组从逻辑上来讲就是一个堆结构，其中，对于下标为i的节点，其左子节点下标为2*i+1，右子节点下标为2*i+2，父节点下标为(i-1)/2。我们用简单的公式来描述一下堆堆定义就是：

\[ \text{大顶堆} : arr[i] \geq arr[2i+1] \And arr[i] \geq arr[2i+2] \]
\[ \text{小顶堆} : arr[i] \leq arr[2i+1] \And arr[i] \leq arr[2i+2] \]

堆排序的基本思想是：

  1. 将待排序的序列构造成一个大顶堆；
  2. 此时，整个序列的最大值就是堆顶的根节点；
  3. 将其与末尾元素进行交换，此时末尾就为最大值；
  4. 然后将剩余的 \(n-1\) 个元素重新构造成一个堆，这样就会得到 \(n\) 个元素的次小值。如此反复执行，便能得到一个有序序列了。

堆排序是一种选择排序，整体主要由构建初始堆 + 交换堆顶元素和末尾元素两部分组成。其中构建初始堆经推导复杂度为 \(O(n)\)，在交换并重建堆的过程中，需交换 \(n-1\)n次，而重建堆的过程中，根据完全二叉树的性质，\(arr[log2(n-1),log2(n-2)...1]\) 逐步递减，近似为 \(nlogn\)。所以堆排序时间复杂度一般认为就是 \(O(nlogn)\) 级。

package main

import "fmt"

func main() {
    fmt.Println("Hello, playground")

    // var nums = []int{4, 2, 3, 1, 5, 6, 7, 8, 9}
    var nums = []int{1, 3, 5, 4, 6, 13}
    heapSort(nums)
    fmt.Println(nums)
}

func heapSort(arr []int) {
    n := len(arr)
    if n <= 1 {
        return
    }

    // 构建最大堆（从最后一个非叶子节点开始）
    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 heapify(arr []int, n, i int) {
    largest := i
    for {
        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 {
            break
        }

        arr[i], arr[largest] = arr[largest], arr[i]
        i = largest // 移动到新的位置
    }
}

评论