golang 堆排序算法

package main

import "fmt"

func main() {
	arr := []int{8, 10, 2, 4, 3, 5, 1, 6, 7}
	fmt.Println(arr)
	heapSort(arr, len(arr))
	fmt.Println(arr)
}

// 堆排序
func heapSort(tree []int, n int) {
	buildHeap(tree, n)
	for i := n - 1; i >= 0; i-- {
		swap(tree, i, 0)
		heapify(tree, i, 0)
	}
}

// 创建堆
func buildHeap(tree []int, n int) {
	lastNode := n - 1
	parent := (lastNode - 1) / 2
	for i := parent; i >= 0; i-- {
		heapify(tree, n, i)
	}
}

// 调整堆
func heapify(tree []int, n, i int) {
	if i >= n {
		return
	}
	c1 := 2*i + 1
	c2 := 2*i + 2
	max := i
	if c1 < n && tree[c1] > tree[max] {
		max = c1
	}
	if c2 < n && tree[c2] > tree[max] {
		max = c2
	}
	if max != i {
		swap(tree, max, i)
		heapify(tree, n, max)
	}
}

// 交换数组位置
func swap(tree []int, i, j int) {
	tree[i], tree[j] = tree[j], tree[i]
}

golang 堆排序算法

原文：https://www.cnblogs.com/Mishell/p/14131009.html