Repository navigation
Expand file tree
/
Copy pathpriorityqueue.go
More file actions
95 lines (86 loc) · 2.31 KB
/
Copy pathpriorityqueue.go
File metadata and controls
95 lines (86 loc) · 2.31 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
package gds
// PriorityQueue is a binary heap where the element for which less(a, b) is
// true has the highest priority and is returned first by Pop.
//
// To create a min-heap of ints:
//
// pq := gds.NewPriorityQueue(func(a, b int) bool { return a < b })
//
// To create a max-heap of ints:
//
// pq := gds.NewPriorityQueue(func(a, b int) bool { return a > b })
//
// It is not safe for concurrent use.
type PriorityQueue[T any] struct {
items []T
less func(a, b T) bool
}
// NewPriorityQueue returns an empty PriorityQueue.
// less(a, b) must return true when a has higher priority than b.
func NewPriorityQueue[T any](less func(a, b T) bool) *PriorityQueue[T] {
return &PriorityQueue[T]{less: less}
}
// Push adds one or more items to the queue.
func (pq *PriorityQueue[T]) Push(items ...T) {
for _, item := range items {
pq.items = append(pq.items, item)
pq.up(len(pq.items) - 1)
}
}
// Pop removes and returns the highest-priority element.
// Returns the zero value and false if the queue is empty.
func (pq *PriorityQueue[T]) Pop() (T, bool) {
if len(pq.items) == 0 {
var zero T
return zero, false
}
top := pq.items[0]
last := len(pq.items) - 1
pq.items[0] = pq.items[last]
pq.items = pq.items[:last]
if len(pq.items) > 0 {
pq.down(0)
}
return top, true
}
// Peek returns the highest-priority element without removing it.
// Returns the zero value and false if the queue is empty.
func (pq *PriorityQueue[T]) Peek() (T, bool) {
if len(pq.items) == 0 {
var zero T
return zero, false
}
return pq.items[0], true
}
// Len returns the number of elements in the queue.
func (pq *PriorityQueue[T]) Len() int { return len(pq.items) }
// IsEmpty reports whether the queue has no elements.
func (pq *PriorityQueue[T]) IsEmpty() bool { return len(pq.items) == 0 }
func (pq *PriorityQueue[T]) up(i int) {
for i > 0 {
parent := (i - 1) / 2
if !pq.less(pq.items[i], pq.items[parent]) {
break
}
pq.items[i], pq.items[parent] = pq.items[parent], pq.items[i]
i = parent
}
}
func (pq *PriorityQueue[T]) down(i int) {
n := len(pq.items)
for {
left := 2*i + 1
if left >= n {
break
}
j := left
if right := left + 1; right < n && pq.less(pq.items[right], pq.items[left]) {
j = right
}
if !pq.less(pq.items[j], pq.items[i]) {
break
}
pq.items[i], pq.items[j] = pq.items[j], pq.items[i]
i = j
}
}