大根堆

父节点大于俩子节点

小根堆

父节点小于俩子节点

大根堆： arr(i)>arr(2i+1) && arr(i)>arr(2i+2)

小根堆： arr(i)<arr(2i+1) && arr(i)<arr(2i+2)

大根堆代码示例

package main

import "fmt"

// 构造堆
func buildHeap(nums []int){
   for i := len(nums)/2; i >= 0  ; i-- {
      heapMaxIfy(nums,i,len(nums))
   }
}

// 调整堆
func heapMaxIfy(nums []int,i,length int){
   left ,right,largest := 2*i+1,2*i+2,i
   //
   if left < length && nums[left] > nums[largest] {
      largest = left
   }
   if right < length && nums[right] > nums[largest] {
      largest = right
   }
   if largest != i {
      nums[i],nums[largest] = nums[largest],nums[i]
      heapMaxIfy(nums,largest,length)
   }
}

// 堆排序
func heapSort(nums []int ){
   // 第一步，从len/2的位置开始构建堆
   buildHeap(nums)
   heapsize := len(nums)
   // 第二步，将堆顶元素与末尾元素交换，末尾的数为最大，剩余待排序数组长度heapsiez-1
   for i := len(nums) -1; i >= 0 ; i-- {
      nums[0],nums[i] = nums[i],nums[0]
      heapsize--
      // 第三步，将剩余的heapsize-1个元素在构建成大根堆，反复执行，即可有序
      heapMaxIfy(nums,0,heapsize)
   }
}
func main() {
   nums := []int{3,2,1,5,6,4}
   heapSort(nums)
   fmt.Println(nums)
}