堆排序

堆排序 算法描述：首先建一个堆，然后调整堆，调整过程是将节点和子节点进行比较，将 其中最大的值变为父节点，递归调整调整次数logn,最后将根节点和尾节点交换再n次 调整O(nlgn).

使用场景

经常用于优先队列即priority_queue 每次入队，出队后都需要堆化。

算法步骤

创建最大堆或者最小堆 调整堆 交换首尾节点(为了维持一个完全二叉树才要进行收尾交换)

示例代码

package main

import "fmt"

func main() {
	arr := []int{1, 9, 10, 30, 2, 5, 45, 8, 65, 9, 355, 123, 88}
	fmt.Println(HeapSort(arr))
}
func HeapSort(arr []int) []int {
	length := len(arr)
	for i := 0; i < length; i++ {
		lastLen := length - i
		HeapSortMax(arr, lastLen)
		if i < length {
			arr[0], arr[lastLen-1] = arr[lastLen-1], arr[0]
		}
	}
	return arr
}
func HeapSortMax(arr []int, length int) []int {
	if length <= 1 {
		return arr
	}
	depth := length/2 - 1
	for i := depth; i >= 0; i-- {
		topMax := i
		leftChild := 2*i + 1
		rightChild := 2*i + 2
		if leftChild <= length-1 && arr[leftChild] > arr[rightChild] {
			topMax = leftChild
		}
		if leftChild <= length-1 && arr[leftChild] < arr[rightChild] {
			topMax = rightChild
		}
		if topMax != i {
			arr[i], arr[topMax] = arr[topMax], arr[i]
		}
	}
	return arr
}