go 堆排序

zzy-777

已于 2022-03-24 09:44:46 修改

阅读量771

点赞数

文章标签：算法

于 2022-03-24 09:44:06 首次发布

本文链接：https://blog.csdn.net/qq_40131465/article/details/123702908

版权

本文介绍了如何使用堆数据结构实现建堆、堆化操作，以及堆排序算法，并通过示例展示了在优先队列中的实际应用。从funcleft和funcright定义的整数运算开始，深入探讨了如何维护最大堆结构，最后通过main函数展示了整个过程的完整流程。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

func left(i int) int {
return 2*i + 1
}

func right(i int) int {
return 2*i + 2
}

//建堆
func buildHeap(a []float64) {
length := len(a)
for i := length / 2; i >= 0; i-- {
maxHeap(i, a, length)
}
}

//堆化，保证每个父节点都大于子节点
func maxHeap(p int, a []float64, length int) {
l := left§
r := right§
index := p
if l < length && a[l] > a[index] {
index = l
}
if r < length && a[r] > a[index] {
index = r
}
if index != p {
a[index], a[p] = a[p], a[index]
maxHeap(index, a, length)
}
}

func main(){
a := []int{1, 5, 6, 4, 7, -8, 77, -9, 6, 1, 0, 3}
buildHeap(a)
fmt.Println(a)
length := len(a)
//堆排，父节点是最大的，每次将父节点放到最后一个元素，再将剩余元素堆化
for length > 0 {
a[0], a[length-1] = a[length-1], a[0]
length–
maxHeap(0, a, length)
}
fmt.Println(a)
}