The highest tagged major version is v2.

dheap

package

v0.0.0-...-f01906e Latest Latest Go to latest Published: Dec 28, 2025 License: Apache-2.0 Imports: 4 Imported by: 0

Details

Valid go.mod file
Redistributable license
Tagged version
Stable version
Learn more about best practices

Repository

github.com/PCfVW/d-Heap-priority-queue

Links

Open Source Insights

Documentation ¶

Overview ¶

Package dheap provides a generic d-ary heap priority queue with O(1) item lookup.

A d-ary heap is a tree structure where:

Each node has at most d children (configurable arity)
The root contains the highest-priority item
Each parent has higher priority than all its children
The tree is complete (filled left-to-right, level by level)

This implementation uses an array-based representation with O(1) item lookup via a map that tracks each item's position in the heap.

Features ¶

Configurable arity (d): number of children per node
Min-heap or max-heap behavior via comparator functions
O(1) item lookup using map for efficient priority updates
O(1) access to highest-priority item
O(log_d n) insert and priority increase operations
O(d · log_d n) pop and priority decrease operations

Cross-Language Compatibility ¶

This Go implementation maintains API parity with:

C++: PriorityQueue<T> in Cpp/PriorityQueue.h
Rust: d_ary_heap::PriorityQueue in Rust/src/lib.rs
Zig: DHeap(T) in zig/src/dheap.zig
TypeScript: PriorityQueue<T> in TypeScript/src/PriorityQueue.ts

All implementations share identical time complexities and method semantics.

Basic Usage ¶

// Create a min-heap by integer value
pq := dheap.New(dheap.Options[int, int]{
	D:            4,
	Comparator:   dheap.MinNumber,
	KeyExtractor: func(x int) int { return x },
})

pq.Insert(5)
pq.Insert(3)
pq.Insert(7)

top, _ := pq.Front()  // Returns 3
pq.Pop()              // Removes 3

Custom Types ¶

type Task struct {
	ID       string
	Priority int
}

pq := dheap.New(dheap.Options[Task, string]{
	D:            4,
	Comparator:   dheap.MinBy(func(t Task) int { return t.Priority }),
	KeyExtractor: func(t Task) string { return t.ID },
})

Reference ¶

Section A.3, d-Heaps, pp. 773–778 of Ravindra Ahuja, Thomas Magnanti & James Orlin, Network Flows (Prentice Hall, 1993).

Version: 2.3.0 License: Apache-2.0 Copyright: 2023-2025 Eric Jacopin

Index ¶

Variables
type Comparator
type KeyExtractor
type Options
type Position
type PriorityQueue
- func New[T any, K comparable](opts Options[T, K]) *PriorityQueue[T, K]
- func WithFirst[T any, K comparable](opts Options[T, K], firstItem T) *PriorityQueue[T, K]

Constants ¶

This section is empty.

Variables ¶

View Source

var ErrEmptyQueue = errors.New("priority queue is empty")

ErrEmptyQueue is returned when attempting to access items in an empty queue.

View Source

var ErrInvalidArity = errors.New("arity (d) must be >= 1")

ErrInvalidArity is returned when arity d < 1.

View Source

var ErrItemNotFound = errors.New("item not found in priority queue")

ErrItemNotFound is returned when an item is not found in the queue.

Functions ¶

This section is empty.

Types ¶

type Comparator ¶

type Comparator[T any] func(a, b T) bool

Comparator returns true if a has higher priority than b.

Cross-language equivalents:

C++: std::less<T> / std::greater<T>
Rust: PriorityCompare<T> trait
Zig: Comparator(T)
TypeScript: Comparator<T> function

var MaxFloat Comparator[float64] = func(a, b float64) bool { return a > b }

MaxFloat is a max-heap comparator for float64 values. Higher numbers have higher priority.

Cross-language equivalents:

TypeScript: maxNumber (for floats)

var MaxFloat32 Comparator[float32] = func(a, b float32) bool { return a > b }

MaxFloat32 is a max-heap comparator for float32 values.

var MaxInt16 Comparator[int16] = func(a, b int16) bool { return a > b }

MaxInt16 is a max-heap comparator for int16 values.

var MaxInt32 Comparator[int32] = func(a, b int32) bool { return a > b }

MaxInt32 is a max-heap comparator for int32 values.

var MaxInt64 Comparator[int64] = func(a, b int64) bool { return a > b }

MaxInt64 is a max-heap comparator for int64 values.

var MaxInt8 Comparator[int8] = func(a, b int8) bool { return a > b }

MaxInt8 is a max-heap comparator for int8 values.

var MaxNumber Comparator[int] = func(a, b int) bool { return a > b }

MaxNumber is a max-heap comparator for int values. Higher numbers have higher priority.

Cross-language equivalents:

TypeScript: maxNumber

var MaxString Comparator[string] = func(a, b string) bool { return a > b }

MaxString is a max-heap comparator for string values. Lexicographically larger strings have higher priority.

Cross-language equivalents:

TypeScript: maxString

var MaxUint Comparator[uint] = func(a, b uint) bool { return a > b }

MaxUint is a max-heap comparator for uint values.

var MinFloat Comparator[float64] = func(a, b float64) bool { return a < b }

MinFloat is a min-heap comparator for float64 values. Lower numbers have higher priority.

Cross-language equivalents:

TypeScript: minNumber (for floats)

var MinFloat32 Comparator[float32] = func(a, b float32) bool { return a < b }

MinFloat32 is a min-heap comparator for float32 values.

var MinInt16 Comparator[int16] = func(a, b int16) bool { return a < b }

MinInt16 is a min-heap comparator for int16 values.

var MinInt32 Comparator[int32] = func(a, b int32) bool { return a < b }

MinInt32 is a min-heap comparator for int32 values.

var MinInt64 Comparator[int64] = func(a, b int64) bool { return a < b }

MinInt64 is a min-heap comparator for int64 values.

var MinInt8 Comparator[int8] = func(a, b int8) bool { return a < b }

MinInt8 is a min-heap comparator for int8 values.

var MinNumber Comparator[int] = func(a, b int) bool { return a < b }

MinNumber is a min-heap comparator for int values. Lower numbers have higher priority.

Cross-language equivalents:

TypeScript: minNumber

var MinString Comparator[string] = func(a, b string) bool { return a < b }

MinString is a min-heap comparator for string values. Lexicographically smaller strings have higher priority.

Cross-language equivalents:

TypeScript: minString

var MinUint Comparator[uint] = func(a, b uint) bool { return a < b }

MinUint is a min-heap comparator for uint values.

func Chain ¶

func Chain[T any](comparators ...Comparator[T]) Comparator[T]

Chain creates a comparator that compares by multiple keys in order. Falls back to subsequent comparators when items are equal.

Example:

// Sort by priority first, then by timestamp
cmp := dheap.Chain(
	dheap.MinBy(func(t Task) int { return t.Priority }),
	dheap.MinBy(func(t Task) int64 { return t.Timestamp }),
)

Cross-language equivalents:

TypeScript: chain(...comparators)

func MaxBy ¶

func MaxBy[T any, K cmp.Ordered](keyFn func(T) K) Comparator[T]

MaxBy creates a max-heap comparator using a key extractor. Higher key values have higher priority (appear closer to root).

Example:

type Task struct {
	ID       string
	Priority int
}
comparator := dheap.MaxBy(func(t Task) int { return t.Priority })

Cross-language equivalents:

Rust: MaxBy<F>
TypeScript: maxBy<T, K>(keyFn)

func MinBy ¶

func MinBy[T any, K cmp.Ordered](keyFn func(T) K) Comparator[T]

MinBy creates a min-heap comparator using a key extractor. Lower key values have higher priority (appear closer to root).

Example:

type Task struct {
	ID       string
	Priority int
}
comparator := dheap.MinBy(func(t Task) int { return t.Priority })

Cross-language equivalents:

Rust: MinBy<F>
TypeScript: minBy<T, K>(keyFn)

func Reverse ¶

func Reverse[T any](cmp Comparator[T]) Comparator[T]

Reverse creates a comparator that reverses another comparator. Useful for converting min-heap to max-heap or vice versa.

Example:

maxByCost := dheap.Reverse(dheap.MinBy(func(t Task) int { return t.Cost }))

Cross-language equivalents:

TypeScript: reverse(cmp)

type KeyExtractor ¶

type KeyExtractor[T any, K comparable] func(item T) K

KeyExtractor extracts a comparable key from an item for O(1) lookup.

The key must be unique per item and stable (not change during the item's lifetime in the queue). This enables O(1) position lookup for priority updates.

type Options ¶

type Options[T any, K comparable] struct {
	// D is the arity (number of children per node). Must be >= 1. Default: 2
	D int

	// Comparator defines priority order. Returns true if first arg has higher priority.
	// Required.
	Comparator Comparator[T]

	// KeyExtractor extracts a unique identity key from each item.
	// Required for O(1) lookup and priority updates.
	KeyExtractor KeyExtractor[T, K]

	// InitialCapacity is a hint for pre-allocation.
	InitialCapacity int
}

Options configures a new PriorityQueue.

Cross-language equivalents:

TypeScript: PriorityQueueOptions<T, K>

type Position ¶

type Position = int

Position is the unified type alias for heap indices (cross-language consistency).

Cross-language equivalents:

C++: TOOLS::PriorityQueue<T>::Position
Rust: d_ary_heap::Position
Zig: DHeap.Position
TypeScript: Position type alias

type PriorityQueue ¶

type PriorityQueue[T any, K comparable] struct {
	// contains filtered or unexported fields
}

PriorityQueue is a generic d-ary heap with O(1) item lookup.

Type Parameters:

T: Item type stored in the queue
K: Key type for identity lookup (must be comparable)

Time Complexities (n = number of items, d = arity):

New(): O(1)
Len(), IsEmpty(), D(): O(1)
Front(), Peek(): O(1)
Contains(), ContainsKey(): O(1)
GetPosition(), GetPositionByKey(): O(1)
Insert(): O(log_d n)
IncreasePriority(): O(log_d n)
Pop(): O(d · log_d n)
DecreasePriority(): O(d · log_d n)
Clear(): O(1)
String(): O(n)

Cross-language equivalents:

C++: TOOLS::PriorityQueue<T, THash, TComparisonPredicate, TEqual>
Rust: d_ary_heap::PriorityQueue<T, C>
Zig: DHeap(T, HashContext(T), Comparator(T))
TypeScript: PriorityQueue<T, K>

func New ¶

func New[T any, K comparable](opts Options[T, K]) *PriorityQueue[T, K]

New creates a new d-ary heap priority queue.

Panics if D < 1 or if Comparator/KeyExtractor is nil.

Example:

pq := dheap.New(dheap.Options[int, int]{
	D:            4,
	Comparator:   dheap.MinNumber,
	KeyExtractor: func(x int) int { return x },
})

Cross-language equivalents:

C++: PriorityQueue<T>(d)
Rust: PriorityQueue::new(d, comparator)
Zig: DHeap.init(d, comparator, allocator)
TypeScript: new PriorityQueue(options)

func WithFirst ¶

func WithFirst[T any, K comparable](opts Options[T, K], firstItem T) *PriorityQueue[T, K]

WithFirst creates a new priority queue with an initial item already inserted.

Equivalent to Rust's with_first() constructor.

Example:

pq := dheap.WithFirst(dheap.Options[int, int]{
	D:            4,
	Comparator:   dheap.MinNumber,
	KeyExtractor: func(x int) int { return x },
}, 42)

Cross-language equivalents:

Rust: PriorityQueue::with_first(d, comparator, item)
TypeScript: PriorityQueue.withFirst(options, item)

func (*PriorityQueue[T, K]) Clear ¶

func (pq *PriorityQueue[T, K]) Clear(newD ...int)

Clear removes all items from the heap, optionally changing the arity.

Time Complexity: O(1)

Cross-language equivalents:

C++: clear(opt_d)
Rust: clear(opt_d)
Zig: clear(new_depth?)
TypeScript: clear(newD?)

func (*PriorityQueue[T, K]) Contains ¶

func (pq *PriorityQueue[T, K]) Contains(item T) bool

Contains checks if an item with the same key exists in the heap.

Time Complexity: O(1)

Cross-language equivalents:

C++: contains(item)
Rust: contains(item)
Zig: contains(item)
TypeScript: contains(item)

func (*PriorityQueue[T, K]) ContainsKey ¶

func (pq *PriorityQueue[T, K]) ContainsKey(key K) bool

ContainsKey checks if an item with the given key exists in the heap.

Time Complexity: O(1)

Cross-language equivalents:

TypeScript: containsKey(key)

func (*PriorityQueue[T, K]) D ¶

func (pq *PriorityQueue[T, K]) D() int

D returns the arity (number of children per node) of the heap.

Time Complexity: O(1)

Cross-language equivalents:

C++: d()
Rust: d()
Zig: d()
TypeScript: d()

func (*PriorityQueue[T, K]) DecreasePriority ¶

func (pq *PriorityQueue[T, K]) DecreasePriority(updatedItem T) error

DecreasePriority updates an existing item to have lower priority (moves toward leaves).

Time Complexity: O(d · log_d n)

Returns ErrItemNotFound if the item is not in the queue.

Note: This method checks both directions for robustness (moveUp then moveDown).

Cross-language equivalents:

C++: decrease_priority(item)
Rust: decrease_priority(item)
Zig: decreasePriority(item)
TypeScript: decreasePriority(item)

func (*PriorityQueue[T, K]) Decrease_priority ¶

func (pq *PriorityQueue[T, K]) Decrease_priority(updatedItem T) error

Decrease_priority is a snake_case alias for DecreasePriority.

func (*PriorityQueue[T, K]) Front ¶

func (pq *PriorityQueue[T, K]) Front() (T, error)

Front returns the highest-priority item without removing it.

Returns ErrEmptyQueue if the heap is empty.

Time Complexity: O(1)

Cross-language equivalents:

C++: front() (UB if empty)
Rust: front() (panics if empty)
Zig: front() (returns null if empty)
TypeScript: front() (throws if empty)

func (*PriorityQueue[T, K]) GetPosition ¶

func (pq *PriorityQueue[T, K]) GetPosition(item T) (Position, bool)

GetPosition returns the current position (index) of an item in the heap.

Time Complexity: O(1)

Cross-language equivalents:

TypeScript: getPosition(item)

func (*PriorityQueue[T, K]) GetPositionByKey ¶

func (pq *PriorityQueue[T, K]) GetPositionByKey(key K) (Position, bool)

GetPositionByKey returns the current position (index) of an item by its key.

Time Complexity: O(1)

Cross-language equivalents:

TypeScript: getPositionByKey(key)

func (*PriorityQueue[T, K]) IncreasePriority ¶

func (pq *PriorityQueue[T, K]) IncreasePriority(updatedItem T) error

IncreasePriority updates an existing item to have higher priority (moves toward root).

Time Complexity: O(log_d n)

Returns ErrItemNotFound if the item is not in the queue.

Note:

For min-heap: decreasing the priority value increases importance.
For max-heap: increasing the priority value increases importance.

Cross-language equivalents:

C++: increase_priority(item)
Rust: increase_priority(item)
Zig: increasePriority(item)
TypeScript: increasePriority(item)

func (*PriorityQueue[T, K]) IncreasePriorityByIndex ¶

func (pq *PriorityQueue[T, K]) IncreasePriorityByIndex(index int)

IncreasePriorityByIndex increases the priority of the item at the given index.

Time Complexity: O(log_d n)

Panics if index is out of bounds.

Cross-language equivalents:

Rust: increase_priority_by_index(index)
TypeScript: increasePriorityByIndex(index)

func (*PriorityQueue[T, K]) Increase_priority ¶

func (pq *PriorityQueue[T, K]) Increase_priority(updatedItem T) error

Increase_priority is a snake_case alias for IncreasePriority.

func (*PriorityQueue[T, K]) Insert ¶

func (pq *PriorityQueue[T, K]) Insert(item T)

Insert adds a new item into the heap according to its priority.

Time Complexity: O(log_d n)

Note: If an item with the same key already exists, behavior is undefined. Use Contains() to check first, or use IncreasePriority()/DecreasePriority() to update existing items.

Cross-language equivalents:

C++: insert(item)
Rust: insert(item)
Zig: insert(item)
TypeScript: insert(item)

func (*PriorityQueue[T, K]) InsertMany ¶

func (pq *PriorityQueue[T, K]) InsertMany(items []T)

InsertMany inserts multiple items into the heap.

Uses heapify algorithm which is O(n) for bulk insertion vs O(n log n) for individual inserts when starting from empty.

Time Complexity: O(n) where n is total items after insertion

Cross-language equivalents:

TypeScript: insertMany(items)

func (*PriorityQueue[T, K]) IsEmpty ¶

func (pq *PriorityQueue[T, K]) IsEmpty() bool

IsEmpty returns true if the heap is empty.

Time Complexity: O(1)

Cross-language equivalents:

C++: is_empty()
Rust: is_empty()
Zig: isEmpty()
TypeScript: isEmpty()

func (*PriorityQueue[T, K]) Is_empty ¶

func (pq *PriorityQueue[T, K]) Is_empty() bool

Is_empty is a snake_case alias for IsEmpty (cross-language consistency).

func (*PriorityQueue[T, K]) Len ¶

func (pq *PriorityQueue[T, K]) Len() int

Len returns the number of items in the heap.

Time Complexity: O(1)

Cross-language equivalents:

C++: len()
Rust: len()
Zig: len()
TypeScript: len()

func (*PriorityQueue[T, K]) Peek ¶

func (pq *PriorityQueue[T, K]) Peek() (T, bool)

Peek returns the highest-priority item without removing it.

Safe alternative to Front(). Returns (item, true) if found, or (zero, false) if empty.

Time Complexity: O(1)

Cross-language equivalents:

Rust: peek()
TypeScript: peek()

func (*PriorityQueue[T, K]) Pop ¶

func (pq *PriorityQueue[T, K]) Pop() (T, bool)

Pop removes and returns the highest-priority item from the heap.

Returns (item, true) if successful, or (zero, false) if the heap is empty.

Time Complexity: O(d · log_d n)

Cross-language equivalents:

C++: pop()
Rust: pop() (no return)
Zig: pop()
TypeScript: pop()

func (*PriorityQueue[T, K]) PopMany ¶

func (pq *PriorityQueue[T, K]) PopMany(count int) []T

PopMany removes and returns multiple highest-priority items.

Time Complexity: O(count · d · log_d n)

Cross-language equivalents:

TypeScript: popMany(count)

func (*PriorityQueue[T, K]) String ¶

func (pq *PriorityQueue[T, K]) String() string

String returns a string representation of the heap contents.

Implements fmt.Stringer interface.

Time Complexity: O(n)

Cross-language equivalents:

C++: to_string() / put(ostream)
Rust: to_string() / Display trait
Zig: toString()
TypeScript: toString()

func (*PriorityQueue[T, K]) ToArray ¶

func (pq *PriorityQueue[T, K]) ToArray() []T

ToArray returns a copy of all items in heap order (not priority order).

Time Complexity: O(n)

Cross-language equivalents:

TypeScript: toArray()

func (*PriorityQueue[T, K]) To_string ¶

func (pq *PriorityQueue[T, K]) To_string() string

To_string is a snake_case alias for String (cross-language consistency).

Source Files ¶

View all Source files

?	: This menu
/	: Search site
f or F	: Jump to
y or Y	: Canonical URL