: jank : : 4995 : 2018-03-06 00:43 数据结构和算法
package main import ( "fmt" ) var heap = []int{1, 33, 23, 3, 425, 24, 11, 333, 98, 93, 2} func Less(a, b int) bool { return heap[a] < heap[b] } func Len() int { return len(heap) } func Swap(a, b int) { heap[a], heap[b] = heap[b], heap[a] } //下沉 // i 父节点 // j1 左儿子 // j2 右二字 func Down(i, n int) { for { j1 := 2*i + 1 if j1 >= n || j1 < 0 { break } j2 := j1 + 1 j := j1 if j2 < n && Less(j2, j) { j = j2 } if Less(i, j) { //如果子节点大于父节点则交换,否则终止此次循环 break } Swap(i, j) i = j } } //创建堆 func MakeHeap() { n := Len() for i := n/2 - 1; i >= 0; i-- { Down(i, n) } } //堆排序 func HeapSort() { n := Len() for i := n - 1; i > 0; i-- { Swap(0, i) //将堆顶元素与末尾元素交换,将最大元素"沉"到数组末端; Down(0, i) //重新调整结构,使其满足堆定义 } } //上浮 func Up(j int) { for { i := (j - 1) / 2 //获取当前节点的父节点 if i == j || Less(i, j) { //判断当前父节点如果大于子节点则退出循环 break } Swap(i, j) j = i } return } //添加数据 func Push(a int) { heap = append(heap, a) Up(Len() - 1) return } //弹出根节点 func Pop() int { n := Len() - 1 Swap(0, n) //交换当前顶点和最后一个数的位置 Down(0, n) //从根节点的左右儿子开始重新对树进行向下排位 old := heap n = len(old) x := old[n-1] heap = old[0 : n-1] return x } //删除节点 func Remove(a int) bool { n := Len() - 1 if a < 0 || a > n { return false } Swap(a, n) heap = heap[0:n] Down(a, n) return true } func main() { MakeHeap() //首先创建堆, // HeapSort() //进行堆排序 fmt.Println(heap) //Push(50) // Push(3) // Push(55) // MakeHeap() HeapSort() // fmt.Println(heap) fmt.Println("添加数字50后:", heap) }