Debian Codegraph @

minheap.go

raw
1 package minheap
2
3 import (
4 "container/heap"
5 )
6
7 // An Element is something we manage in a priority queue.
8 type Element struct {
9 Value interface{}
10 Priority int // The priority of the item in the queue.
11 // The index is needed by update and is maintained by the heap.Interface methods.
12 index int // The index of the item in the heap.
13 }
14
15 // A PriorityQueue implements heap.Interface and holds Items.
16 type MinHeap []*Element
17
18 func NewMinHeap() *MinHeap {
19 mh := &MinHeap{}
20 heap.Init(mh)
21 return mh
22 }
23
24 func (mh MinHeap) Len() int { return len(mh) }
25
26 func (mh MinHeap) Less(i, j int) bool {
27 return mh[i].Priority < mh[j].Priority
28 }
29
30 func (mh MinHeap) Swap(i, j int) {
31 mh[i], mh[j] = mh[j], mh[i]
32 mh[i].index = i
33 mh[j].index = j
34 }
35
36 func (mh *MinHeap) Push(x interface{}) {
37 n := len(*mh)
38 item := x.(*Element)
39 item.index = n
40 *mh = append(*mh, item)
41 }
42
43 func (mh *MinHeap) Pop() interface{} {
44 old := *mh
45 n := len(old)
46 item := old[n-1]
47 item.index = -1 // for safety
48 *mh = old[0 : n-1]
49 return item
50 }
51
52 func (mh *MinHeap) PushEl(el *Element) {
53 heap.Push(mh, el)
54 }
55
56 func (mh *MinHeap) PopEl() *Element {
57 el := heap.Pop(mh)
58 return el.(*Element)
59 }
60
61 func (mh *MinHeap) PeekEl() *Element {
62 items := *mh
63 return items[0]
64 }
65
66 // update modifies the priority and value of an Item in the queue.
67 func (mh *MinHeap) UpdateEl(el *Element, priority int) {
68 heap.Remove(mh, el.index)
69 el.Priority = priority
70 heap.Push(mh, el)
71 }
72
73 func (mh *MinHeap) RemoveEl(el *Element) {
74 heap.Remove(mh, el.index)
75 }