Golang堆排序实现原理与完整代码

堆排序核心概念

堆是一种基于数组实现的特殊完全二叉树结构。其核心性质是每个节点的值都必须大于或小于其子节点的值：

• 大顶堆（Max Heap）：每个节点的值大于其左右子节点的值，根节点为最大值。
• 小顶堆（Min Heap）：每个节点的值小于其左右子节点的值，根节点为最小值。

由于堆是完全二叉树，它可以通过紧凑的数组形式存储，便于索引计算。[9,8,9,8,7,6,4,1,2,0] 这种结构的数组对应的二叉树形态如下：

准备条件：数组索引关系

假设数组 nums 的长度为 len，在处理堆结构时需遵循以下下标映射规则：

• 最后一个节点的父节点下标：len/2 - 1。
• 任意下标 n 的子节点下标：
• 左子节点（lson）：n*2 + 1
• 右子节点（rson）：n*2 + 2

注意：当计算出的子节点下标 >= len 时，表示越界，即该位置不存在子节点。

操作顺序与算法实现

堆排序主要分为两步：构建初始堆，以及逐步提取极值完成排序。以“大顶堆”为例说明具体操作。

第1步：构建初始最大堆

目的：将无序数组调整为一个符合大顶堆性质的结构。

入口与动作：

1. 从数组末尾开始，定位第一个非叶子节点，即下标为 len/2 - 1 的位置。
2. 自底向上遍历所有非叶子节点。对于当前节点 parent：

• 获取其左右子节点的下标。
• 比较 parent 与左右子节点的值，找出三者中的最大值（若存在子节点）。
• 如果最大值不是 parent，则交换它们，并对被交换到的子节点递归调用此调整过程，确保其子树仍满足堆性质。

关键参数：需实时传入数组长度 len，防止在局部调整时操作到已排序的元素区间之外。

func buildHeep(nums []int, len int) {
	// 找到最后一个节点的父节点
	parent := len/2 - 1
	for parent >= 0 {
		heapify(nums, parent, len)
		parent--
	}
}

func heapify(nums []int, parent, len int) {
	max := parent
	lson := parent*2 + 1
	rson := parent*2 + 2
	if lson < len && nums[lson] > nums[max] {
		max = lson
	}
	if rson < len && nums[rson] > nums[max] {
		max = rson
	}
	if parent != max {
		swap(&nums[max], &nums[parent])
		heapify(nums, max, len)
	}
}

第2步：执行堆排序

目的：利用构建好的堆获得有序的数组序列。

入口与动作：

1. 此时根节点 nums[0] 必定是剩余未排序部分的最大值。
2. 将根节点与当前区间的最后一个元素交换。这样，最大值就被固定到了数组的正确位置。
3. 减少有效区间长度（i--），忽略已固定的最后一个元素，对剩下的 i-1 个元素重新执行 第1步 的堆构建过程。
4. 重复上述过程，直到有效区间长度小于2。

func HeapSort(nums []int) []int {
	i := len(nums)
	for i > 1 {
		buildHeep(nums, i) // 重新建堆
		swap(&nums[0], &nums[i-1]) // 将最大值放到末尾
		i-- // 缩小考虑范围
	}
	return nums
}

每次交换和重建树的过程示意如下：

完整代码集成

以下为包含核心逻辑与测试用例的 Go 语言完整代码示例。

// structpk/heap.go
package structpk
import "fmt"

/*
	给定整数数组nums和k，
	请返回数组中第k个最大元素，
	请注意，你需要找的是数组排序后的第k个最大元素，
	而不是第k个不同的元素
*/
func swap(a, b *int) {
	*a, *b = *b, *a
}

func HeapSort(nums []int) []int {
	i := len(nums)
	for i > 1 {
		buildHeep(nums, i)
		swap(&nums[0], &nums[i-1])
		i--
	}
	return nums
}
func buildHeep(nums []int, len int) {
	parent := len/2 - 1
	for parent >= 0 {
		heapify(nums, parent, len)
		parent--
	}
	fmt.Println(nums[0:len])
}
func heapify(nums []int, parent, len int) {
	max := parent
	lson := parent*2 + 1
	rson := parent*2 + 2
	if lson < len && nums[lson] > nums[max] {
		max = lson
	}
	if rson < len && nums[rson] > nums[max] {
		max = rson
	}
	if parent != max {
		swap(&nums[max], &nums[parent])
		heapify(nums, max, len)
	}
}

// main.go:
package main
import (
	"demo/structpk"
	"fmt"
)
func main() {
	fmt.Println(structpk.HeapSort([]int{
		3, 5, 3, 0, 8, 6,
	}))
}

总结

Golang 堆排序的关键在于正确理解完全二叉树的父子索引关系。通过先 buildHeep 建立大顶堆，再循环将堆顶（最大值）移至数组末端并重调整，即可高效完成原地排序。以上就是关于 Golang 中堆排序的实现原理与完整代码的详细内容，更多关于 Go 语言算法的资料请关注本站其它相关文章！