blob: 2d09add84262f2b9955519bb3ce4ac3a18521b0f (
about) (
plain) (
blame)
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
|
package priorityqueue
// Queue is one slice-backed priority queue.
//
// Labels: MT-Unsafe.
type Queue[T any] struct {
items []T
less func(left, right T) bool
}
// New builds one empty priority queue ordered by less.
func New[T any](less func(left, right T) bool) *Queue[T] {
return &Queue[T]{less: less}
}
// Len reports the number of queued items.
func (queue *Queue[T]) Len() int {
return len(queue.items)
}
// Pop removes one highest-priority item.
func (queue *Queue[T]) Pop() (T, bool) {
if len(queue.items) == 0 {
var zero T
return zero, false
}
last := len(queue.items) - 1
top := queue.items[0]
queue.items[0] = queue.items[last]
queue.items = queue.items[:last]
if len(queue.items) > 0 {
queue.siftDown(0)
}
return top, true
}
// Push inserts one item.
func (queue *Queue[T]) Push(item T) {
queue.items = append(queue.items, item)
queue.siftUp(len(queue.items) - 1)
}
|
