README
¶
kpqs 
A generic keyed priority queue where priority is derived from the item itself.
The kpqs package provides a stable, key-addressable priority queue for arbitrary types. Each item is assigned a priority via a user-provided function. Items are inserted with a key (derived from the item), and duplicates are overwritten.
✨ Features
- ✅ Key-based access (update, delete, contains)
- ✅ Priority derived from item field or logic
- ✅ Stable ordering: earlier enqueued wins on tie
- ✅ Comparator injection (
MinFirst,MaxFirst, etc.) - ❌ No external priority control at enqueue time
🧱 Example
package main
import (
"fmt"
"github.com/byExist/priorityqueues/kpqs"
)
type Task struct {
ID string
Priority int
}
func main() {
q := kpqs.New(
kpqs.StableMinFirst[*Task, int],
func(t *Task) string { return t.ID },
func(t *Task) int { return t.Priority },
)
kpqs.Enqueue(q, &Task{ID: "a", Priority: 3})
kpqs.Enqueue(q, &Task{ID: "b", Priority: 1})
kpqs.Enqueue(q, &Task{ID: "c", Priority: 2})
for kpqs.Len(q) > 0 {
task, _ := kpqs.Dequeue(q)
fmt.Println(task.ID)
}
}
// Output:
// b
// c
// a
📚 Use When
- You want a keyed queue (e.g.,
map[ID]*Task) - Each item knows its own priority
- You need stable, deterministic dequeue order
🚫 Avoid If
- You want to provide priority externally → use
kmpqs - You don’t need keys or updates → use
mpqsorpqs
🔍 Comparator Options
Use one of the following with New(...):
kpqs.MinFirst[T, P]kpqs.MaxFirst[T, P]kpqs.StableMinFirst[T, P]kpqs.StableMaxFirst[T, P]
You can also provide a custom comparator function.
Documentation
¶
Index ¶
- func Clear[K comparable, T any, P cmp.Ordered](pq *PriorityQueue[K, T, P])
- func Contains[K comparable, T any, P cmp.Ordered](pq *PriorityQueue[K, T, P], item T) bool
- func Delete[K comparable, T any, P cmp.Ordered](pq *PriorityQueue[K, T, P], item T) bool
- func Dequeue[K comparable, T any, P cmp.Ordered](pq *PriorityQueue[K, T, P]) (T, bool)
- func Enqueue[K comparable, T any, P cmp.Ordered](pq *PriorityQueue[K, T, P], item T)
- func Len[K comparable, T any, P cmp.Ordered](pq *PriorityQueue[K, T, P]) int
- func MaxFirst[T any, P cmp.Ordered](x, y Elem[T, P]) bool
- func MinFirst[T any, P cmp.Ordered](x, y Elem[T, P]) bool
- func Peek[K comparable, T any, P cmp.Ordered](pq *PriorityQueue[K, T, P]) (T, bool)
- func StableMaxFirst[T any, P cmp.Ordered](x, y Elem[T, P]) bool
- func StableMinFirst[T any, P cmp.Ordered](x, y Elem[T, P]) bool
- func Update[K comparable, T any, P cmp.Ordered](pq *PriorityQueue[K, T, P], item T) bool
- type Elem
- type PriorityQueue
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func Clear ¶
func Clear[K comparable, T any, P cmp.Ordered](pq *PriorityQueue[K, T, P])
Example ¶
package main
import (
"fmt"
"github.com/byExist/priorityqueues/kpqs"
)
func main() {
type Task struct {
ID string
Priority int
}
pq := kpqs.New(
kpqs.MinFirst[*Task, int],
func(t *Task) string { return t.ID },
func(t *Task) int { return t.Priority },
)
kpqs.Enqueue(pq, &Task{ID: "t1", Priority: 1})
kpqs.Enqueue(pq, &Task{ID: "t2", Priority: 2})
fmt.Println("len before:", kpqs.Len(pq))
kpqs.Clear(pq)
fmt.Println("len after:", kpqs.Len(pq))
}
Output: len before: 2 len after: 0
func Contains ¶
func Contains[K comparable, T any, P cmp.Ordered](pq *PriorityQueue[K, T, P], item T) bool
Example ¶
package main
import (
"fmt"
"github.com/byExist/priorityqueues/kpqs"
)
func main() {
type Task struct {
ID string
Priority int
}
pq := kpqs.New(
kpqs.MinFirst[*Task, int],
func(t *Task) string { return t.ID },
func(t *Task) int { return t.Priority },
)
t := &Task{ID: "t1", Priority: 1}
kpqs.Enqueue(pq, t)
fmt.Println(kpqs.Contains(pq, t))
}
Output: true
func Delete ¶
func Delete[K comparable, T any, P cmp.Ordered](pq *PriorityQueue[K, T, P], item T) bool
Example ¶
package main
import (
"fmt"
"github.com/byExist/priorityqueues/kpqs"
)
func main() {
type Task struct {
ID string
Priority int
}
pq := kpqs.New(
kpqs.MinFirst[*Task, int],
func(t *Task) string { return t.ID },
func(t *Task) int { return t.Priority },
)
t := &Task{ID: "t1", Priority: 1}
kpqs.Enqueue(pq, t)
ok := kpqs.Delete(pq, t)
fmt.Println("deleted:", ok)
fmt.Println("len:", kpqs.Len(pq))
}
Output: deleted: true len: 0
func Dequeue ¶
func Dequeue[K comparable, T any, P cmp.Ordered](pq *PriorityQueue[K, T, P]) (T, bool)
func Enqueue ¶
func Enqueue[K comparable, T any, P cmp.Ordered](pq *PriorityQueue[K, T, P], item T)
Example (DequeuePeek) ¶
package main
import (
"fmt"
"github.com/byExist/priorityqueues/kpqs"
)
func main() {
type Task struct {
ID string
Priority int
}
pq := kpqs.New(
kpqs.MinFirst[*Task, int],
func(t *Task) string { return t.ID },
func(t *Task) int { return t.Priority },
)
kpqs.Enqueue(pq, &Task{ID: "t1", Priority: 2})
kpqs.Enqueue(pq, &Task{ID: "t2", Priority: 1})
item, _ := kpqs.Peek(pq)
fmt.Println("peek:", item.ID)
item, _ = kpqs.Dequeue(pq)
fmt.Println("dequeue:", item.ID)
}
Output: peek: t2 dequeue: t2
func Len ¶
func Len[K comparable, T any, P cmp.Ordered](pq *PriorityQueue[K, T, P]) int
func Peek ¶
func Peek[K comparable, T any, P cmp.Ordered](pq *PriorityQueue[K, T, P]) (T, bool)
func Update ¶
func Update[K comparable, T any, P cmp.Ordered](pq *PriorityQueue[K, T, P], item T) bool
Example ¶
package main
import (
"fmt"
"github.com/byExist/priorityqueues/kpqs"
)
func main() {
type Task struct {
ID string
Priority int
}
pq := kpqs.New(
kpqs.MinFirst[*Task, int],
func(t *Task) string { return t.ID },
func(t *Task) int { return t.Priority },
)
t := &Task{ID: "t1", Priority: 5}
kpqs.Enqueue(pq, t)
t.Priority = 1
kpqs.Update(pq, t)
item, _ := kpqs.Peek(pq)
fmt.Println(item.ID)
}
Output: t1
Types ¶
type PriorityQueue ¶
type PriorityQueue[K comparable, T any, P cmp.Ordered] struct { // contains filtered or unexported fields }
func New ¶
func New[K comparable, T any, P cmp.Ordered]( lessFunc func(x, y Elem[T, P]) bool, keyFunc func(T) K, prioFunc func(T) P, ) *PriorityQueue[K, T, P]
Example ¶
package main
import (
"fmt"
"github.com/byExist/priorityqueues/kpqs"
)
func main() {
type Task struct {
ID string
Priority int
}
keyFunc := func(t *Task) string { return t.ID }
prioFunc := func(t *Task) int { return t.Priority }
pq := kpqs.New(
kpqs.StableMinFirst[*Task, int],
keyFunc,
prioFunc,
)
kpqs.Enqueue(pq, &Task{ID: "t1", Priority: 2})
kpqs.Enqueue(pq, &Task{ID: "t2", Priority: 2})
kpqs.Enqueue(pq, &Task{ID: "t3", Priority: 1})
first, _ := kpqs.Dequeue(pq)
second, _ := kpqs.Dequeue(pq)
fmt.Println(first.ID)
fmt.Println(second.ID)
}
Output: t3 t1
Source Files
Click to show internal directories.
Click to hide internal directories.