golang 使用双向链表作为container/heap的载体

MyHeap：container/heap的数据载体，需要实现以下方法：

Len：堆中数据个数

Less：第i个元素 是否必 第j个元素 值小

Swap：交换第i个元素和 第j个元素

Push：向堆中追加元素

Pop：从堆中取出元素

下面是使用双向链路作为数据载体的最小堆实现方式：

package mainimport ("container/heap""fmt"
)type HeapItem struct {Value intPrev  *HeapItemNext  *HeapItem
}type MyHeap struct {Head   *HeapItemTail   *HeapItemLength int
}func (h *MyHeap) Len() int {return h.Length
}func (h *MyHeap) Less(i, j int) bool {return h.Find(i).Value < h.Find(j).Value
}func (h *MyHeap) Swap(i, j int) {nodeI, nodeJ := h.Find(i), h.Find(j)isNear := h.IsNear(nodeI, nodeJ)// 记录I的前和后nodeIPrev, nodeINext := nodeI.Prev, nodeI.Next// 记录J的前和后nodeJPrev, nodeJNext := nodeJ.Prev, nodeJ.Next// 把J放到I的位置nodeIPrev.Next = nodeJnodeJ.Prev = nodeIPrevnodeJ.Next = nodeINext // near, 对于相邻元素, 这样操作有问题, 下面会重新赋值nodeINext.Prev = nodeJ // near, 对于相邻元素, 这样操作有问题, 下面会重新赋值// 把I放到J的位置nodeJPrev.Next = nodeI // near, 对于相邻元素, 这样操作有问题, 下面会重新赋值nodeI.Prev = nodeJPrev // near, 对于相邻元素, 这样操作有问题, 下面会重新赋值nodeI.Next = nodeJNextnodeJNext.Prev = nodeI// 对于相邻元素，重新赋值if isNear {nodeJ.Next = nodeInodeINext.Prev = nodeIPrevnodeJPrev.Next = nodeJNextnodeI.Prev = nodeJ}
}func (h *MyHeap) Push(v interface{}) {newItem := v.(*HeapItem)temp := h.Tail.Prevtemp.Next = newItemnewItem.Prev = tempnewItem.Next = h.Tailh.Tail.Prev = newItemh.Length++return
}func (h *MyHeap) Pop() interface{} {realTailNode := h.Tail.PrevrealTailNode.Prev.Next = realTailNode.NextrealTailNode.Next.Prev = realTailNode.Prevh.Length--return realTailNode
}func (h *MyHeap) IsNear(nodeI, nodeJ *HeapItem) bool {if nodeI.Next == nodeJ {return true}return false
}func (h *MyHeap) Find(i int) *HeapItem {nodeI := h.Headfor k := 0; k <= i; k++ {nodeI = nodeI.Next}return nodeI
}func (h *MyHeap) Show() {forward := ""backward := ""i := 0for curr := h.Head; curr != nil && i < 10; curr = curr.Next {forward += fmt.Sprintf("'%d'->", curr.Value)i++}j := 0for curr := h.Tail; curr != nil && j < 10; curr = curr.Prev {backward = fmt.Sprintf("'%d'<-", curr.Value) + backwardj++}fmt.Printf("forward=%s, backward=%s\n", forward, backward)
}func InitHeap() *MyHeap {head := &HeapItem{Value: -1}tail := &HeapItem{Value: -2}head.Next = tailtail.Prev = headreturn &MyHeap{Head:   head,Tail:   tail,Length: 0,}
}func main() {myHeap := InitHeap()heap.Init(myHeap)heap.Push(myHeap, &HeapItem{Value: 10})heap.Push(myHeap, &HeapItem{Value: 1000})heap.Push(myHeap, &HeapItem{Value: 5})heap.Push(myHeap, &HeapItem{Value: 1})heap.Push(myHeap, &HeapItem{Value: 7})myHeap.Show()for myHeap.Len() > 0 {item := heap.Pop(myHeap).(*HeapItem)fmt.Printf("%d ", item.Value)}fmt.Println()
}