internal/priorityqueue/sift.go


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

package priorityqueue

func (queue *Queue[T]) siftDown(idx int) {
	for {
		left := idx*2 + 1
		if left >= len(queue.items) {
			return
		}

		best := left

		right := left + 1
		if right < len(queue.items) && queue.less(queue.items[right], queue.items[left]) {
			best = right
		}

		if !queue.less(queue.items[best], queue.items[idx]) {
			return
		}

		queue.items[idx], queue.items[best] = queue.items[best], queue.items[idx]
		idx = best
	}
}

func (queue *Queue[T]) siftUp(idx int) {
	for idx > 0 {
		parent := (idx - 1) / 2
		if !queue.less(queue.items[idx], queue.items[parent]) {
			return
		}

		queue.items[idx], queue.items[parent] = queue.items[parent], queue.items[idx]
		idx = parent
	}
}