[数据结构与算法]堆及堆排序

堆是一种二叉树的形式

分为大顶堆和小顶堆

性质：

①完全二叉树

②父节点≥或≤子节点

可以用数组来存储堆
父节点：（i-1）/2，
左子节点：2 * i+1，
右子节点：2 * i+2，

维护堆的性质

//维护堆的性质 (小顶堆) 把大的交换到下面去
func heapify(arr []int, root int) {
	len := len(arr)
	max := root //父节点
	left := root*2 + 1
	right := root*2 + 2
	if right < len && arr[right] < arr[max] {
		max = right
	}
	if left < len && arr[left] < arr[max] {
		max = left
	}
	if max != root {
		arr[max], arr[root] = arr[root], arr[max]
		heapify(arr, max) //递归维护
	}
}

建堆

//建堆
func Init(arr *[]int) {
	for i := len(*arr)-1; i >= 0; i-- {
		heapify(*arr, i)
	}
	return
}

堆排序

//堆排序
func heapsort(arr []int) {
	lenth := len(arr)
	for i := lenth - 1; i >= 0; i-- {
		arr[i], arr[0] = arr[0], arr[i]
		heapify(arr[:i], 0)
	}
}