Go语言的OOP,接口,接口的组合,基础库的函数及接口如何抽象设计,这些东西在Go的Heap源码及演示例子处理中,都有很好的展示. 在"container/heap"中,它的接口是如下定义的:
type Interface interface {sort.InterfacePush(x interface{}) // add x as element Len()Pop() interface{} // remove and return element Len() – 1. } 我不太明白为啥是这样的设计,只好通过下面的方法来尝试了解. 1. 通过测试例子,了解使用方式. 2. 试图还原原始场景,即利用源码整合实现了一个原始的堆排序
然后通过这两者的对比,来慢慢体会.
container/heap的测试例子:
package mainimport ("container/heap""fmt""sort")// An IntHeap is a min-heap of ints.type IntHeap []intfunc (h IntHeap) Len() int{ return len(h) }func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }func (h IntHeap) Swap(i, j int){ h[i], h[j] = h[j], h[i] }func (h *IntHeap) Push(x interface{}) {// Push and Pop use pointer receivers because they modify the slice's length,// not just its contents.*h = append(*h, x.(int))}func (h *IntHeap) Pop() interface{} {old := *hn := len(old)x := old[n-1]*h = old[0 : n-1]return x}// This example inserts several ints into an IntHeap, checks the minimum,// and removes them in order of priority.func main() {h := &IntHeap{100,16,4,8,70,2,36,22,5,12}fmt.Println("\nHeap:")heap.Init(h)fmt.Printf("最小值: %d\n", (*h)[0])//for(Pop)依次输出最小值,则相当于执行了HeapSortfmt.Println("\nHeap sort:")for h.Len() > 0 {fmt.Printf("%d ", heap.Pop(h))}//增加一个新值,然后输出看看fmt.Println("\nPush(h, 3),然后输出堆看看:")heap.Push(h, 3)for h.Len() > 0 {fmt.Printf("%d ", heap.Pop(h))}fmt.Println("\n使用sort.Sort排序:")h2 := IntHeap{100,16,4,8,70,2,36,22,5,12}sort.Sort(h2)for _,v := range h2 {fmt.Printf("%d ",v)}}/*输出结果:———————————–Heap:最小值: 2Heap sort:2 4 5 8 12 16 22 36 70 100Push(h, 3),然后输出堆看看:3使用sort.Sort排序:2 4 5 8 12 16 22 36 70 100*/
自定义的类,实现相关接口后,交由heap.Init()去构建堆. 从堆中Pop()后,数据就被从heap中移除了. 升降序由Less()来决定. 自定义类也可以直接用Sort来排序,因为实现了相关接口.
再看下我手工整合实现的堆排序代码:
package main//Heap//author:Xiong Chuan Liang//date:2015-2-4import ("fmt")var( heap = []int{100,16,4,8,70,2,36,22,5,12})func main(){fmt.Println("\n数组:")Print(heap)MakeHeap()fmt.Println("\n构建树后:")Print(heap)fmt.Println("\n增加 90,30,1 :")Push(90)Push(30)Push(1)Print(heap)n := Pop()fmt.Println("\nPop出最小值(",n,")后:")Print(heap)fmt.Println("\nRemove()掉idx为3即值",heap[3-1],"后:")Remove(3)Print(heap)fmt.Println("\nHeapSort()后:")HeapSort()Print(heap)}func Print(arr []int){for _,v := range arr {fmt.Printf("%d ",v)}}//构建堆func MakeHeap(){n := len(heap)for i := n/2-1 ;i >= 0;i–{down(i, n)}}//由父节点至子节点依次建堆//parent: i//left child : 2*i+1//right child : 2*i+2func down(i,n int) {//构建最小堆,父小于两子节点值for {j1 := 2*i + 1if j1 >= n || j1 < 0 { // j1 < 0 after int overflowbreak}//找出两个节点中最小的(less: a<b)j := j1 // left childif j2 := j1 + 1; j2 < n && !Less(j1, j2) {j = j2 // = 2*i + 2 // right child}//然后与父节点i比较,如果父节点小于这个子节点最小值,则break,否则swapif !Less(j, i) {break}Swap(i, j)i = j}}//由子节点至父节点依次重建堆func up(j int) {for {i := (j – 1) / 2 // parentif i == j || !Less(j, i) {//less(子,父) !Less(9,5) == true//父节点小于子节点,符合最小堆条件,breakbreak}//子节点比父节点小,互换Swap(i, j)j = i}}func Push(x interface{}){heap = append(heap, x.(int))up(len(heap)-1)return }func Pop() interface{} {n := len(heap) – 1Swap(0, n)down(0, n)old :=heapn = len(old)x := old[n-1]heap = old[0 : n-1]return x}func Remove(i int) interface{} {n := len(heap) – 1if n != i {Swap(i, n)down(i, n)up(i)}return Pop()}func Less(a,b int)bool{return heap[a] < heap[b]func Swap(a,b int){heap[a],heap[b] = heap[b],heap[a]}func HeapSort(){//升序 Less(heap[a] > heap[b])//最大堆//降序 Less(heap[a] < heap[b])//最小堆for i := len(heap)-1 ;i > 0;i–{//移除顶部元素到数组末尾,然后剩下的重建堆,依次循环Swap(0, i)down(0, i)}}/*输出结果:———————————–数组:100 16 4 8 70 2 36 22 5 12构建树后:2 5 4 8 12 100 36 22 16 70增加 90,30,1 :1 5 2 8 12 4 36 22 16 70 90 100 30Pop出最小值( 1 )后:2 5 4 8 12 30 36 22 16 70 90 100Remove()掉idx为3即值 4 后:4 5 8 16 12 30 36 22 100 70 90HeapSort()后:100 90 70 36 30 22 16 12 8 5 4*/
人的一生要疯狂一次，无论是为一个人，一段情，一段旅途，或一个梦想。
