README
¶
Name
queue - priority queue
Description
Queue package holds different implementation of Priority Queue (PQ) with parameterized less function to create MaxPQ or MinPQ.
The discussions and comments imply MaxPQ.
Implementations
-
Unordered array [lazy]: store items in the array in undefined order. Push() appends a new item to the end. Search for the maximum item for Pop() and Top().
-
Ordered array [eager]: store items in a sorted array. Push() inserts the item at appropriate position (like insert sort). Pop() and Top() retrieve the last item.
-
Binary heap [eager]: store items in a heap-ordered complete binary tree. Push() appends the new item to the end and promotes it all the way to the root item as long is the parent is less than or equal to the new item. Pop() removes the root item, moves the last one to the root and demotes the new root with the max child. It continues demotion process until the end of array.
-
Map binary heap [eager]: a key-value map with keys sorted using a binary heap.
Performance
| Implementation | Insert | Pop |
|---|---|---|
| Unordered array | 1 | N |
| Ordered array | N | 1 |
| Binary heap | ln(N) | ln(N) |
| Map Binary heap | ln(N) | ln(N) |
Documentation
¶
Index ¶
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type BinaryHeapPQ ¶
type BinaryHeapPQ[T comparable] struct { // contains filtered or unexported fields }
BinaryHeapPQ implements a PriorityQueue using a heap-ordered binary tree.
Heap-ordered binary tree stores binary tree in layers. An item at index i stores its children at indices 2*i and 2*i+1, both guaranteed to be less than or equal to the i-th item.
Unlike OrderedArrayPQ and UnorderedArrayPQ, heap-ordered binary tree achieves O(log(N)) time complexity by keeping the order of items on Push() and Pop():
- Push() adds new element tot he end of the array and promotes it to the parent node iteratively as long as less(i/2,i)==true for it.
- Pop() moves the root item to the end, deletes the last item from the array, and restores the order by demoting the root item all the way through the array as long as at least one child node is larger than the i-th item starting from the root. It picks up the largest child to guaranteed the invariant that both children are less than or equal to the parent node.
func NewBinaryHeapPQ ¶
func NewBinaryHeapPQ[T comparable](less LessFunc[T]) *BinaryHeapPQ[T]
NewBinaryHeapPQ constructs a BinaryHeapPQ.
Example ¶
package main
import (
"fmt"
"iter"
"math/rand/v2"
"slices"
"github.com/skhal/lab/book/algos/c2/s4/queue"
)
type PriorityQueue[T comparable] interface {
Empty() bool
Pop()
Push(T)
Size() int
Top() T
}
func collect[T comparable](s []T, pq PriorityQueue[T], maxSize int) []T {
for _, item := range s {
pq.Push(item)
if pq.Size() > maxSize {
pq.Pop()
}
}
popAll := func(pq PriorityQueue[T]) iter.Seq[T] {
return func(yield func(T) bool) {
for !pq.Empty() {
v := pq.Top()
pq.Pop()
if !yield(v) {
break
}
}
}
}
s = slices.Collect(popAll(pq))
slices.Reverse(s)
return s
}
type NewPQFunc[T comparable] func(queue.LessFunc[T]) PriorityQueue[T]
func example[T comparable](s []T, newPQFn NewPQFunc[T], less func(x, y T) bool) {
const maxSize = 3
for _, e := range []struct {
name string
less queue.LessFunc[T]
}{
{
name: "max",
less: func(x, y T) bool { return less(y, x) },
},
{
name: "min",
less: less,
},
} {
pq := newPQFn(e.less)
fmt.Printf("%s %d items: %v\n", e.name, maxSize, collect(s, pq, maxSize))
}
}
func main() {
newPQ := func(less queue.LessFunc[int]) PriorityQueue[int] {
return queue.NewBinaryHeapPQ(less)
}
less := func(x, y int) bool { return x < y }
example(rand.Perm(100), newPQ, less)
}
Output: max 3 items: [99 98 97] min 3 items: [0 1 2]
func (*BinaryHeapPQ[T]) Empty ¶
func (pq *BinaryHeapPQ[T]) Empty() bool
func (*BinaryHeapPQ[T]) Pop ¶
func (pq *BinaryHeapPQ[T]) Pop()
func (*BinaryHeapPQ[T]) Push ¶
func (pq *BinaryHeapPQ[T]) Push(v T)
func (*BinaryHeapPQ[T]) Size ¶
func (pq *BinaryHeapPQ[T]) Size() int
func (*BinaryHeapPQ[T]) Top ¶
func (pq *BinaryHeapPQ[T]) Top() T
type LessFunc ¶
type LessFunc[T comparable] func(x, y T) bool
LessFunc compares two items and returns true if x is logically less than y.
type MapBinaryHeapPQ ¶
type MapBinaryHeapPQ[K comparable, V any] struct { // contains filtered or unexported fields }
MapBinaryHeapPQ is a key-value map that stores keys in a heap-oriented binary-tree priority queue.
Example ¶
// Multiway merge combines N sorted arrays using a priority queue to pick up
// the next array with min element.
//
// The PQ stores (item, slice-tail).
pq := queue.NewMapBinaryHeapPQ[int, []int](func(x, y int) bool {
// Emultate MinPQ to pick up the next smallest item
return lessInt(y, x)
})
for _, nn := range [][]int{
{1, 5, 7, 9},
{2, 6},
{3, 4, 8},
} {
pq.Push(nn[0], nn[1:])
}
var sorted []int
for !pq.Empty() {
n, nn := pq.Top()
pq.Pop()
sorted = append(sorted, n)
if len(nn) == 0 {
continue
}
pq.Push(nn[0], nn[1:])
}
fmt.Println(sorted)
Output: [1 2 3 4 5 6 7 8 9]
func NewMapBinaryHeapPQ ¶
func NewMapBinaryHeapPQ[K comparable, V any](fn LessFunc[K]) *MapBinaryHeapPQ[K, V]
NewMapBinaryHeapPQ creates a MapBinaryHeapPQ with a given keys comparison function.
func (*MapBinaryHeapPQ[K, V]) Empty ¶
func (pq *MapBinaryHeapPQ[K, V]) Empty() bool
Empty reports whether the map is empty.
func (*MapBinaryHeapPQ[K, V]) Pop ¶
func (pq *MapBinaryHeapPQ[K, V]) Pop()
Pop removes the key-value pair with "max" key.
func (*MapBinaryHeapPQ[K, V]) Push ¶
func (pq *MapBinaryHeapPQ[K, V]) Push(k K, v V)
Push inserts a new key-value pair into the map.
func (*MapBinaryHeapPQ[K, V]) Size ¶
func (pq *MapBinaryHeapPQ[K, V]) Size() int
Size reports the number of key-value pairs in the map.
func (*MapBinaryHeapPQ[K, V]) Top ¶
func (pq *MapBinaryHeapPQ[K, V]) Top() (K, V)
Top returns the key-value pair with "max" key.
type OrderedArrayPQ ¶
type OrderedArrayPQ[T comparable] struct { // contains filtered or unexported fields }
OrderedArrayPQ keeps elements sorted by less function. This fact speeds up access to or remove of the top element at the expense of maintaining the order at the insertion.
func NewOrderedArrayPQ ¶
func NewOrderedArrayPQ[T comparable](f LessFunc[T]) *OrderedArrayPQ[T]
NewOrderedArrayPQ stores a Priority Queue in ordered array.
Example ¶
package main
import (
"fmt"
"iter"
"math/rand/v2"
"slices"
"github.com/skhal/lab/book/algos/c2/s4/queue"
)
type PriorityQueue[T comparable] interface {
Empty() bool
Pop()
Push(T)
Size() int
Top() T
}
func collect[T comparable](s []T, pq PriorityQueue[T], maxSize int) []T {
for _, item := range s {
pq.Push(item)
if pq.Size() > maxSize {
pq.Pop()
}
}
popAll := func(pq PriorityQueue[T]) iter.Seq[T] {
return func(yield func(T) bool) {
for !pq.Empty() {
v := pq.Top()
pq.Pop()
if !yield(v) {
break
}
}
}
}
s = slices.Collect(popAll(pq))
slices.Reverse(s)
return s
}
type NewPQFunc[T comparable] func(queue.LessFunc[T]) PriorityQueue[T]
func example[T comparable](s []T, newPQFn NewPQFunc[T], less func(x, y T) bool) {
const maxSize = 3
for _, e := range []struct {
name string
less queue.LessFunc[T]
}{
{
name: "max",
less: func(x, y T) bool { return less(y, x) },
},
{
name: "min",
less: less,
},
} {
pq := newPQFn(e.less)
fmt.Printf("%s %d items: %v\n", e.name, maxSize, collect(s, pq, maxSize))
}
}
func main() {
newPQ := func(less queue.LessFunc[int]) PriorityQueue[int] {
return queue.NewOrderedArrayPQ(less)
}
less := func(x, y int) bool { return x < y }
example(rand.Perm(100), newPQ, less)
}
Output: max 3 items: [99 98 97] min 3 items: [0 1 2]
func (*OrderedArrayPQ[T]) Empty ¶
func (pq *OrderedArrayPQ[T]) Empty() bool
func (*OrderedArrayPQ[T]) Pop ¶
func (pq *OrderedArrayPQ[T]) Pop()
func (*OrderedArrayPQ[T]) Push ¶
func (pq *OrderedArrayPQ[T]) Push(v T)
func (*OrderedArrayPQ[T]) Size ¶
func (pq *OrderedArrayPQ[T]) Size() int
func (*OrderedArrayPQ[T]) Top ¶
func (pq *OrderedArrayPQ[T]) Top() T
type UnorderedArrayPQ ¶
type UnorderedArrayPQ[T comparable] struct { // contains filtered or unexported fields }
UnorderedArrayPQ stores items in a slice unordered. It restores the order by placing the top item to the end of the slice for fast access on either Pop() or Top() call.
func NewUnorderedArrayPQ ¶
func NewUnorderedArrayPQ[T comparable](less LessFunc[T]) *UnorderedArrayPQ[T]
NewUnorderedArrayPQ stores a Priority Queue in unordered array.
Example ¶
package main
import (
"fmt"
"iter"
"math/rand/v2"
"slices"
"github.com/skhal/lab/book/algos/c2/s4/queue"
)
type PriorityQueue[T comparable] interface {
Empty() bool
Pop()
Push(T)
Size() int
Top() T
}
func collect[T comparable](s []T, pq PriorityQueue[T], maxSize int) []T {
for _, item := range s {
pq.Push(item)
if pq.Size() > maxSize {
pq.Pop()
}
}
popAll := func(pq PriorityQueue[T]) iter.Seq[T] {
return func(yield func(T) bool) {
for !pq.Empty() {
v := pq.Top()
pq.Pop()
if !yield(v) {
break
}
}
}
}
s = slices.Collect(popAll(pq))
slices.Reverse(s)
return s
}
type NewPQFunc[T comparable] func(queue.LessFunc[T]) PriorityQueue[T]
func example[T comparable](s []T, newPQFn NewPQFunc[T], less func(x, y T) bool) {
const maxSize = 3
for _, e := range []struct {
name string
less queue.LessFunc[T]
}{
{
name: "max",
less: func(x, y T) bool { return less(y, x) },
},
{
name: "min",
less: less,
},
} {
pq := newPQFn(e.less)
fmt.Printf("%s %d items: %v\n", e.name, maxSize, collect(s, pq, maxSize))
}
}
func main() {
newPQ := func(less queue.LessFunc[int]) PriorityQueue[int] {
return queue.NewUnorderedArrayPQ(less)
}
less := func(x, y int) bool { return x < y }
example(rand.Perm(100), newPQ, less)
}
Output: max 3 items: [99 98 97] min 3 items: [0 1 2]
func (*UnorderedArrayPQ[T]) Empty ¶
func (pq *UnorderedArrayPQ[T]) Empty() bool
func (*UnorderedArrayPQ[T]) Pop ¶
func (pq *UnorderedArrayPQ[T]) Pop()
func (*UnorderedArrayPQ[T]) Push ¶
func (pq *UnorderedArrayPQ[T]) Push(v T)
func (*UnorderedArrayPQ[T]) Size ¶
func (pq *UnorderedArrayPQ[T]) Size() int
func (*UnorderedArrayPQ[T]) Top ¶
func (pq *UnorderedArrayPQ[T]) Top() T
Source Files