魔方 网站,苏州网站制作开发公司,wordpress精简,七牛云最新消息MyHeap#xff1a;container/heap的数据载体#xff0c;需要实现以下方法#xff1a;
Len#xff1a;堆中数据个数
Less#xff1a;第i个元素 是否必 第j个元素 值小
Swap#xff1a;交换第i个元素和 第j个元素
Push#xff1a;向堆中追加元素
Pop#xff1a;从堆…MyHeapcontainer/heap的数据载体需要实现以下方法
Len堆中数据个数
Less第i个元素 是否必 第j个元素 值小
Swap交换第i个元素和 第j个元素
Push向堆中追加元素
Pop从堆中取出元素
下面是使用双向链路作为数据载体的最小堆实现方式
package mainimport (container/heapfmt
)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.Lengthreturn
}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()
}
