mpqs

README

mpqs

A generic, manually prioritized queue with stability.

The mpqs package provides a priority queue implementation where the user explicitly provides the priority value for each item. It supports custom types, stable ordering (tie-breaking by insertion order), and comparator injection.

---

✨ Features

• ✅ Generic over item type (T) and priority type (P)
• ✅ External priority injection per enqueue
• ✅ Stable ordering for equal priority values
• ✅ Custom comparator support (min, max, stable variants)
• ❌ No key-based lookup or update support

---

🧱 Example

package main

import (
	"fmt"
	"github.com/byExist/priorityqueues/mpqs"
)

type Task struct {
	ID   string
	Desc string
}

func main() {
	q := mpqs.New(mpqs.StableMinFirst[*Task, int])

	tasks := []*Task{
		{ID: "t1", Desc: "send email"},
		{ID: "t2", Desc: "render image"},
		{ID: "t3", Desc: "generate report"},
	}

	// External priorities (lower means higher priority)
	mpqs.Enqueue(q, tasks[0], 3) // email
	mpqs.Enqueue(q, tasks[1], 2) // image
	mpqs.Enqueue(q, tasks[2], 1) // report

	for mpqs.Len(q) > 0 {
		task, _ := mpqs.Dequeue(q)
		fmt.Println(task.ID, ":", task.Desc)
	}
}

// Output:
// t3 : generate report
// t2 : render image
// t1 : send email

---

📚 Use When

• You want full control over priority values at enqueue time
• You need stable ordering among equal-priority items
• You don't need key-based access or updates

---

🚫 Avoid If

• You need to identify/update/delete items by key → use kpqs or kmpqs
• Your item inherently contains its own priority → use kpqs
• You want a minimal value-only queue → use pqs

---

🔍 Comparator Options

Use one of the following with New(...):

• mpqs.MinFirst[T, P]
• mpqs.MaxFirst[T, P]
• mpqs.StableMinFirst[T, P]
• mpqs.StableMaxFirst[T, P]

You can also provide a custom comparator function.

Documentation

Overview

Example (ReversedStableMinHeap)

package main

import (
	"fmt"

	"github.com/byExist/priorityqueues/mpqs"
)

func main() {
	reversedStable := func(x, y mpqs.Elem[string, int]) bool {
		if x.Priority() == y.Priority() {
			return x.Sequence() > y.Sequence()
		}
		return x.Priority() < y.Priority()
	}

	pq := mpqs.New(reversedStable)

	mpqs.Enqueue(pq, "a", 1)
	mpqs.Enqueue(pq, "b", 2)
	mpqs.Enqueue(pq, "c", 2)

	first, _ := mpqs.Dequeue(pq)
	second, _ := mpqs.Dequeue(pq)
	third, _ := mpqs.Dequeue(pq)

	fmt.Println(first)
	fmt.Println(second)
	fmt.Println(third)

}

Output:

a
c
b

Index

• func Clear[T any, P cmp.Ordered](pq *PriorityQueue[T, P])
• func Dequeue[T any, P cmp.Ordered](pq *PriorityQueue[T, P]) (T, bool)
• func Enqueue[T any, P cmp.Ordered](pq *PriorityQueue[T, P], item T, prio P)
• func Len[T any, P cmp.Ordered](pq *PriorityQueue[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[T any, P cmp.Ordered](pq *PriorityQueue[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
• type Elem
  • func (e Elem[T, P]) Item() T
  • func (e Elem[T, P]) Priority() P
  • func (e Elem[T, P]) Sequence() int
• type PriorityQueue
  • func New[T any, P cmp.Ordered](lessFunc func(x, y Elem[T, P]) bool) *PriorityQueue[T, P]

Examples

• Package (ReversedStableMinHeap)
• Clear
• Dequeue
• Enqueue
• Len
• New
• Peek

Functions

func Clear

func Clear[T any, P cmp.Ordered](pq *PriorityQueue[T, P])

Example

package main

import (
	"fmt"

	"github.com/byExist/priorityqueues/mpqs"
)

func main() {
	pq := mpqs.New(mpqs.MinFirst[string, int])
	mpqs.Enqueue(pq, "task", 1)
	mpqs.Clear(pq)
	fmt.Println(mpqs.Len(pq))
}

Output:

0

func Dequeue

func Dequeue[T any, P cmp.Ordered](pq *PriorityQueue[T, P]) (T, bool)

Example

package main

import (
	"fmt"

	"github.com/byExist/priorityqueues/mpqs"
)

func main() {
	pq := mpqs.New(mpqs.MinFirst[string, int])
	mpqs.Enqueue(pq, "task1", 2)
	mpqs.Enqueue(pq, "task2", 1)
	item, _ := mpqs.Dequeue(pq)
	fmt.Println(item)
}

Output:

task2

func Enqueue

func Enqueue[T any, P cmp.Ordered](pq *PriorityQueue[T, P], item T, prio P)

Example

package main

import (
	"fmt"

	"github.com/byExist/priorityqueues/mpqs"
)

func main() {
	pq := mpqs.New(mpqs.MinFirst[string, int])
	mpqs.Enqueue(pq, "task", 10)
	item, _ := mpqs.Peek(pq)
	fmt.Println(item)
}

Output:

task

func Len

func Len[T any, P cmp.Ordered](pq *PriorityQueue[T, P]) int

Example

package main

import (
	"fmt"

	"github.com/byExist/priorityqueues/mpqs"
)

func main() {
	pq := mpqs.New(mpqs.MinFirst[string, int])
	fmt.Println(mpqs.Len(pq))
	mpqs.Enqueue(pq, "a", 1)
	fmt.Println(mpqs.Len(pq))
}

Output:

0
1

func MaxFirst

func MaxFirst[T any, P cmp.Ordered](x, y Elem[T, P]) bool

func MinFirst

func MinFirst[T any, P cmp.Ordered](x, y Elem[T, P]) bool

func Peek

func Peek[T any, P cmp.Ordered](pq *PriorityQueue[T, P]) (T, bool)

Example

package main

import (
	"fmt"

	"github.com/byExist/priorityqueues/mpqs"
)

func main() {
	pq := mpqs.New(mpqs.MinFirst[string, int])
	mpqs.Enqueue(pq, "task", 1)
	item, _ := mpqs.Peek(pq)
	fmt.Println(item)
}

Output:

task

func StableMaxFirst

func StableMaxFirst[T any, P cmp.Ordered](x, y Elem[T, P]) bool

func StableMinFirst

func StableMinFirst[T any, P cmp.Ordered](x, y Elem[T, P]) bool

Types

type Elem

type Elem[T any, P cmp.Ordered] struct {
	// contains filtered or unexported fields
}

func (Elem[T, P]) Item

func (e Elem[T, P]) Item() T

func (Elem[T, P]) Priority

func (e Elem[T, P]) Priority() P

func (Elem[T, P]) Sequence

func (e Elem[T, P]) Sequence() int

type PriorityQueue

type PriorityQueue[T any, P cmp.Ordered] struct {
	// contains filtered or unexported fields
}

func New

func New[T any, P cmp.Ordered](
	lessFunc func(x, y Elem[T, P]) bool,
) *PriorityQueue[T, P]

Example

package main

import (
	"fmt"

	"github.com/byExist/priorityqueues/mpqs"
)

func main() {
	pq := mpqs.New(mpqs.MinFirst[string, int])
	mpqs.Enqueue(pq, "task1", 2)
	mpqs.Enqueue(pq, "task2", 1)
	item, _ := mpqs.Dequeue(pq)
	fmt.Println(item)
}

Output:

task2