Documentation
¶
Overview ¶
Package pq provides a priority queue implementation that aims to simplify the use of priority queues in Go. The package implements a MinPQ, MaxPQ, and a generic PQ that can be initialized with a custom less function, as well as a priority queue interface that can be used to initialize a priority queue with any container that implements pq.Interface.
Index ¶
- type Interface
- type PQ
- func (pq *PQ[V]) All() iter.Seq[V]
- func (pq *PQ[V]) Drain() iter.Seq[V]
- func (pq *PQ[V]) IsEmpty() bool
- func (pq *PQ[V]) Len() int
- func (pq *PQ[V]) Merge(other *PQ[V])
- func (pq *PQ[V]) Pop() V
- func (pq *PQ[V]) Push(val ...V)
- func (pq *PQ[V]) Remove(i int) V
- func (pq *PQ[V]) String() string
- func (pq PQ[V]) Top() V
- func (pq *PQ[V]) Update(i int, val V)
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type PQ ¶
type PQ[V any] struct { // contains filtered or unexported fields }
PQ is a priority queue implementation that uses a heap.Interface to manage the elements in the priority queue. The priority queue can be initialized as a min heap, max heap, or with a custom less function.
func NewMaxPQ ¶
func NewMaxPQ[V constraints.Ordered](vals ...V) *PQ[V]
NewMaxPQ creates a new max heap. If vals are provided, they are added to the heap, and the heap is initialized.
Example ¶
package main
import (
"fmt"
"github.com/elordeiro/goext/containers/pq"
)
func main() {
pq := pq.NewMaxPQ(7, 3, 1, 5)
for v := range pq.All() {
fmt.Println(v)
}
}
Output: 7 5 3 1
func NewMinPQ ¶
func NewMinPQ[V constraints.Ordered](vals ...V) *PQ[V]
NewMinPQ creates a new min heap. If vals are provided, they are added to the heap, and the heap is initialized.
Example ¶
package main
import (
"fmt"
"github.com/elordeiro/goext/containers/pq"
)
func main() {
pq := pq.NewMinPQ(7, 3, 1, 5)
for v := range pq.All() {
fmt.Println(v)
}
}
Output: 1 3 5 7
func NewPQFrom ¶
NewPQFrom creates a new priority queue from an existing PQ.Interface and values. The values are added to the heap and the heap is initialized.
func NewPQFunc ¶
NewPQFunc creates a new custom priority queue that can be used for items that are not ordered as per the definition of constraints.Ordered. If vals are provided, they are added to the heap, and the heap is initialized. The less function is used to determine the priority of the elements in the priority queue.
Example ¶
package main
import (
"fmt"
"github.com/elordeiro/goext/containers/pq"
"github.com/elordeiro/goext/containers/tuples"
)
func main() {
pq := pq.NewPQFunc(func(item1, item2 tuples.Pair[string, int]) bool {
return item1.Right() > item2.Right()
})
pq.Push(tuples.NewPair("banana", 7))
pq.Push(tuples.NewPair("orange", 3))
pq.Push(tuples.NewPair("apple", 1))
pq.Push(tuples.NewPair("grape", 5))
for v := range pq.All() {
fmt.Println(v)
}
}
Output: (banana 7) (grape 5) (orange 3) (apple 1)
func (*PQ[V]) All ¶
All returns an iter.Seq[V] of values in the priority queue in priority order.
Example ¶
package main
import (
"fmt"
"github.com/elordeiro/goext/containers/pq"
)
func main() {
pq := pq.NewMaxPQ(7, 3, 1, 5)
for v := range pq.All() {
fmt.Println(v)
}
}
Output: 7 5 3 1
func (*PQ[V]) Drain ¶
Drain returns an iter.Seq[V] of values in the priority queue in priority order by popping all the values from the priority queue. The priority queue is empty after calling Drain. It returns a single use iterator.
func (*PQ[V]) IsEmpty ¶
IsEmpty returns true if the priority queue is empty
Example ¶
package main
import (
"fmt"
"github.com/elordeiro/goext/containers/pq"
)
func main() {
pq := pq.NewMaxPQ[int]()
fmt.Println(pq.IsEmpty())
pq.Push(1)
fmt.Println(pq.IsEmpty())
}
Output: true false
func (*PQ[V]) Len ¶
Len returns the number of elements in the priority queue
Example ¶
package main
import (
"fmt"
"github.com/elordeiro/goext/containers/pq"
)
func main() {
pq := pq.NewMaxPQ(7, 3, 1, 5)
fmt.Println(pq.Len())
}
Output: 4
func (*PQ[V]) Merge ¶
Merge merges the priority queue with another priority queue and returns a new priority queue.
func (*PQ[V]) Pop ¶
func (pq *PQ[V]) Pop() V
Pop removes and returns the element with the highest priority
Example ¶
package main
import (
"fmt"
"github.com/elordeiro/goext/containers/pq"
)
func main() {
pq := pq.NewMaxPQ(7, 3, 1, 5)
fmt.Println(pq.Pop())
fmt.Println(pq.Pop())
fmt.Println(pq.Pop())
fmt.Println(pq.Pop())
}
Output: 7 5 3 1
func (*PQ[V]) Push ¶
func (pq *PQ[V]) Push(val ...V)
Push adds an element to the priority queue
Example ¶
package main
import (
"fmt"
"github.com/elordeiro/goext/containers/pq"
)
func main() {
pq := pq.NewMaxPQ(7, 3, 1, 5)
pq.Push(9)
for v := range pq.All() {
fmt.Println(v)
}
}
Output: 9 7 5 3 1
func (*PQ[V]) Remove ¶
Remove removes and returns the element at index i from the priority queue
Example ¶
package main
import (
"fmt"
"github.com/elordeiro/goext/containers/pq"
)
func main() {
pq := pq.NewMaxPQ(7, 3, 1, 5)
fmt.Println(pq.Remove(1))
for v := range pq.All() {
fmt.Println(v)
}
}
Output: 5 7 3 1
func (*PQ[V]) String ¶
String returns a string representation of the priority queue
Example ¶
package main
import (
"fmt"
"github.com/elordeiro/goext/containers/pq"
)
func main() {
pq := pq.NewMaxPQ(7, 3, 1, 5)
fmt.Println(pq)
}
Output: ![7 5 1 3]
func (PQ[V]) Top ¶
func (pq PQ[V]) Top() V
Top returns the element with the highest priority without removing it.
Example ¶
package main
import (
"fmt"
"github.com/elordeiro/goext/containers/pq"
)
func main() {
pq := pq.NewMaxPQ(7, 3, 1, 5)
fmt.Println(pq.Top())
pq.Pop()
fmt.Println(pq.Top())
}
Output: 7 5
func (*PQ[V]) Update ¶
Update updates the value at index i in the priority queue and re-establishes the heap ordering with a call to Fix. As per the container/heap documentation, changing the value of the element at index i and then calling Fix is equivalent to, but less expensive than, calling Remove(i) followed by a Push of the new value
Example ¶
package main
import (
"fmt"
"github.com/elordeiro/goext/containers/pq"
)
func main() {
pq := pq.NewMaxPQ(9, 3, 5, 7)
pq.Update(0, 1)
for v := range pq.All() {
fmt.Println(v)
}
}
Output: 7 5 3 1
Source Files