Go语言的官方package里面提供了"container/heap"，在该package里面定义了Heap（堆）这一数据结构的使用接口。只要自定义的数据类型实现了标准接口，可以很方便的对自定义的数据类型在堆中进行排序了。

堆结构的接口为：

type Interface interface { 	sort.Interface 	Push(x interface{}) // add x as element Len() 	Pop() interface{}   // remove and return element Len() - 1. } 

同时sort.Interface接口为：

type Interface interface { 	// Len is the number of elements in the collection. 	Len() int 	// Less reports whether the element with 	// index i should sort before the element with index j. 	Less(i, j int) bool 	// Swap swaps the elements with indexes i and j. 	Swap(i, j int) } 

因此为了使用自定义的堆结构，需要定义5个接口函数。

在实践中期望构造一个使用堆排序的定时器队列，能够按照堆顶的元素快速获得最近的任务触发时间：

type element struct { 	TaskId    string 	Expire    time.Time 	... }  type eleHeap []*element 

构造自定义的堆结构接口：

func (h eleHeap) Len() int           { return len(h) } func (h eleHeap) Less(i, j int) bool { return h[i].Expire.Before(h[j].Expire) } func (h eleHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }  func (h *eleHeap) Push(x interface{}) { 	// Push and Pop use pointer receivers because they modify the slice's length, 	// not just its contents. 	*h = append(*h, x.(*element)) }  func (h *eleHeap) Pop() interface{} { 	old := *h 	n := len(old) 	x := old[n-1]		// 为什么Pop是取slice最末元素？ 	*h = old[0 : n-1]   // 难道Golang的堆不是最小堆吗？ 	return x }  

在此之后就可以使用Heap的公共函数来对自定义的堆结构进行Pop和Push操作了。

to := time.NewTimer(WaitInterval) hp := &eleHeap{} // 定义变量 heap.Init(hp)	 // 堆结构初始化 for { 	select { 		case ele := <-TaskChan: 			heap.Push(hp, ele) // 入堆 			to.Reset(0) 		case <-to.C: 			for hp.Len() != 0 { 				ele, ok := heap.Pop(hp).(*element) // 出堆 				if ok { 					if time.Now().Before(ele.Expire) { 						heap.Push(hp, ele) // 时辰未到，再次入堆 						to.Reset(ele.Expire.Sub(now)) 						break 					} 					// time expired, do task 					... 				} 			} 		} 	} } 

在使用堆的过程中，对于为何在自定义的Pop过程中，取出的是队列中最末元素有些不解。自定义的Push过程也是将元素放在最末，那么Pop过程理所应当从队列头部取出经过上浮、下沉操作后堆中最小（大）的元素。经过查看"container/heap"的源码，终于揭开了这一谜题。

首先看一下堆的上浮、下沉操作：

func up(h Interface, j int) { 	for { 		i := (j - 1) / 2 // parent 		if i == j || !h.Less(j, i) { 			break 		} 		// 在上浮过程中，从较大的节点j开始，与其父节点进行比较 		// 若不小于其父节点，则与其父节点进行交换 		h.Swap(i, j) 		j = i 	} }  func down(h Interface, i0, n int) bool { 	i := i0 	for { 		j1 := 2*i + 1 		if j1 >= n || j1 < 0 { // j1 < 0 after int overflow 			break 		} 		j := j1 // left child 		if j2 := j1 + 1; j2 < n && !h.Less(j1, j2) { 			j = j2 // = 2*i + 2  // right child 		} 		if !h.Less(j, i) { 			break 		} 		// 在下沉过程中，从较小的i0节点开始，与其两个子节点进行比较 		// 若小于其中一个子节点，则与较小的子节点进行交换 		h.Swap(i, j) 		i = j 	} 	return i > i0 } 

上浮和下沉过程还是十分标准的，再看一下Push和Pop过程：

func Push(h Interface, x interface{}) { 	h.Push(x)        // 使用自定义的Push接口，将元素放入队列尾部 	up(h, h.Len()-1) // 将新放入的元素进行上浮操作 }  func Pop(h Interface) interface{} { 	n := h.Len() - 1 	h.Swap(0, n)     // 交换队列中头和尾元素 	down(h, 0, n)    // 将原队列的尾元素在h.Len() - 1的新队列中进行下沉 	return h.Pop()   // 弹出交换后的尾元素 } 

由此可见，对于自定义Pop函数理解的错误还是因为自身对于堆结构的思维定势导致的。 如果Heap.Pop过程中，先获得头元素的值，再将尾元素放入队列头进行下沉，则自定义的Pop才是返回队列头元素。

真相只有一个~