堆排序

关键：k[i]>=k[2i]&&k[i]>=k[2*i+1] 父节点大于子节点这是大根堆。

堆可以被看成是一棵树，结点在堆中的高度可以被定义为从本结点到叶子结点的最长简单下降路径上边的数目；定义堆的高度为树根的高度。我们将看到，堆结构上的一些基本操作的运行时间至多是与树的高度成正比，为O（lgn）

利用堆排序，分两步：

1构建堆

2获取堆顶

package main

import (
   "fmt"
)

func main() {
   arr := []int{0, 1, 2, 3, 4, 5, 6, 7}

   for length := len(arr); length > 0; length-- {
      buildBigHeap(arr, length)
      fmt.Print(arr)
      change(&arr[0], &arr[length-1])
      fmt.Print("***")
      fmt.Print(arr)
      fmt.Println("-----------")
   }

}

/**
建立大顶堆
 */
func buildBigHeap(arr []int, len int) {
   //for parent node
   //k[i]>=k[2i]&&k[i]>=k[2*i+1]

   count := 0
   for to := len - 1; to > 0; to-- {
      node := to
      for parent := obtainParent(node); node > 0; node, parent = parent, obtainParent(node) {
         if arr[parent] < arr[node] {
            change(&arr[parent], &arr[node])
            count++
         }
      }
   }
   fmt.Println(count)
}

func change(a *int, b *int) {
   temp := *a;
   *a = *b
   *b = temp
}

/**
获取父节点下标
 */
func obtainParent(child int) int {
   //数组下标从1开始
   //parent=node/2
   //从0开始
   //parent+1=(node+1)/2==>parent=(node+1)/2-1

   return (child+1)/2 - 1
}