41 lines
967 B
Go
41 lines
967 B
Go
package main
|
|
|
|
import "sort"
|
|
|
|
type priorityQueue[T any] struct {
|
|
elems []*T
|
|
less func(a, b *T) bool
|
|
maxDepth int
|
|
totalEnqueue int
|
|
totalDequeue int
|
|
}
|
|
|
|
// PriorityQueue implements a simple slice based queue.
|
|
// less is the function for sorting. reverse a and b to reverse the sort.
|
|
// T is the item
|
|
// U is a slice of T
|
|
func PriorityQueue[T any](less func(a, b *T) bool) *priorityQueue[T] {
|
|
return &priorityQueue[T]{less: less}
|
|
}
|
|
func (pq *priorityQueue[T]) Insert(elem *T) {
|
|
pq.totalEnqueue++
|
|
|
|
pq.elems = append(pq.elems, elem)
|
|
pq.maxDepth = max(pq.maxDepth, len(pq.elems))
|
|
}
|
|
func (pq *priorityQueue[T]) IsEmpty() bool {
|
|
return len(pq.elems) == 0
|
|
}
|
|
func (pq *priorityQueue[T]) ExtractMin() *T {
|
|
pq.totalDequeue++
|
|
|
|
var elem *T
|
|
if pq.IsEmpty() {
|
|
return elem
|
|
}
|
|
|
|
sort.Slice(pq.elems, func(i, j int) bool { return pq.less(pq.elems[j], pq.elems[i]) })
|
|
pq.elems, elem = pq.elems[:len(pq.elems)-1], pq.elems[len(pq.elems)-1]
|
|
return elem
|
|
}
|