堆排序

通用问题

• 时间复杂度：$O(n\log n)$
  • 建堆：$O(n)$
  • heapify：$O(\log n)$
  • 对 n 个数进行 heapfiy()
• 空间复杂度：$O(1)$
• 稳定性：不稳定

性质

• 完全二叉树
• 大根堆:每个节点的值都大于或者等于他的左右孩子节点的值

存储

• 使用数组存储
• 下标从 0 开始
  • i 的左孩子：$i\ast 2+1$
  • i 的右孩子：$i\ast 2+2$
  • i 的父节点：$\frac{i-1}{2}$

代码实现

package mySort

import "fmt"

func heapfiy(arr []int, n, i int) {
	largest := i
	lson := i*2 + 1
	rson := i*2 + 2
	if lson < n && arr[largest] < arr[lson] {
		largest = lson
	}
	if rson < n && arr[largest] < arr[rson] {
		largest = rson
	}
	if largest != i {
		arr[largest], arr[i] = arr[i], arr[largest]
		heapfiy(arr, n, largest)
	}
}

func HeapSort(arr []int) {
	//建堆
	n := len(arr)
	//最后一个父节点：(n-2)/2=n/2-1
	for i := n/2 - 1; i >= 0; i-- {
		heapfiy(arr, n, i)
	}
	//排序
	for i := n - 1; i >= 0; i-- {
		arr[i], arr[0] = arr[0], arr[i]
		heapfiy(arr, i, 0)
	}
}

func TsetHeapSort() {
	arr := []int{3, 8, 14, 5, 2, 16, 8, 7, 6}
	fmt.Println(arr)
	HeapSort(arr)
	fmt.Println(arr)
}

扩展

维护一个大顶堆（优先队列）:编程开发/Golang/算法调用与实现/优先队列（小根堆）