通用问题

  • 时间复杂度:
    • 建堆:
    • heapify:
    • 对 n 个数进行 heapfiy()
  • 空间复杂度:
  • 稳定性:不稳定

性质

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

存储

  • 使用数组存储
  • 下标从 0 开始
    • i 的左孩子:
    • i 的右孩子:
    • i 的父节点:

代码实现

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)
}
 

扩展

维护一个大顶堆(优先队列):优先队列(小根堆)