通用问题 时间复杂度:O(nlogn) 建堆:O(n) heapify:O(logn) 对 n 个数进行 heapfiy() 空间复杂度:O(1) 稳定性:不稳定 性质 完全二叉树 大根堆:每个节点的值都大于或者等于他的左右孩子节点的值 存储 使用数组存储 下标从 0 开始 i 的左孩子:i∗2+1 i 的右孩子:i∗2+2 i 的父节点:2i−1 代码实现 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) } 扩展 维护一个大顶堆(优先队列):优先队列(小根堆)