heapcraft

package module
v0.2.0 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Jun 29, 2025 License: MIT Imports: 10 Imported by: 0

README

heapcraft logo

heapcraft is a Go library offering a suite of heap data structures which include binary, d‑ary, pairing, radix, skew, and leftist heaps.

Available heap types include:

D-ary Heaps:

  • DaryHeap / SyncDaryHeap

Radix Heaps:

  • RadixHeap / SyncRadixHeap

Tree-Based Heaps:

  • PairingHeap / SyncPairingHeap
  • FullPairingHeap / SyncFullPairingHeap
  • SkewHeap / SyncSkewHeap
  • FullSkewHeap / SyncFullSkewHeap
  • LeftistHeap / SyncLeftistHeap
  • FullLeftistHeap / SyncFullLeftistHeap

✨ Features

Category Details
Heap Variants Binary, D‑ary, Pairing, Radix, Skew, Leftist
Implementation Types Regular/Full for Pairing, Skew, and Leftist heaps; Single for D‑ary, and Radix heaps
Thread Safety Both non-thread-safe and thread-safe versions available (e.g., DaryHeap and SyncDaryHeap)
Generics Go 1.18+ type parameters—store any custom type
Node Tracking Full implementations maintain a map for O(1) lookup and update operations
Memory Pooling Optional object pooling
Examples Examples for each heap type in the examples/ directory

🚀 Getting Started

Install

go get github.com/galactixx/heapcraft@latest

Then import it in your code:

import "github.com/galactixx/heapcraft"

🔍 API

Implementation Types

D-ary Heaps (DaryHeap / SyncDaryHeap) provide array-based heap operations:

  • Push(value, priority) - Add elements
  • Pop() / PopValue() / PopPriority() - Remove elements
  • Peek() / PeekValue() / PeekPriority() - View without removing
  • Length(), IsEmpty(), Clear(), Clone()
  • Update(index, value, priority) - Update element at index
  • Remove(index) - Remove element at index
  • PopPush(value, priority) - Pop and push in one operation
  • PushPop(value, priority) - Push and pop in one operation
  • Register(fn) / Deregister(id) - Callback registration for swaps

Radix Heaps (RadixHeap / SyncRadixHeap) provide monotonic priority queue operations:

  • Push(value, priority) - Add elements (must be >= last popped priority)
  • Pop() / PopValue() / PopPriority() - Remove elements
  • Peek() / PeekValue() / PeekPriority() - View without removing
  • Length(), IsEmpty(), Clear(), Clone()
  • Rebalance() - Manually trigger bucket rebalancing
  • Merge(other) - Merge with another radix heap

Regular Tree-Based Heaps (PairingHeap / SyncPairingHeap, SkewHeap / SyncSkewHeap, LeftistHeap / SyncLeftistHeap) provide:

  • Push(value, priority) - Add elements
  • Pop() / PopValue() / PopPriority() - Remove elements
  • Peek() / PeekValue() / PeekPriority() - View without removing
  • Length(), IsEmpty(), Clear(), Clone()

Full Tree-Based Heaps (FullPairingHeap / SyncFullPairingHeap, FullSkewHeap / SyncFullSkewHeap, FullLeftistHeap / SynFullcLeftistHeap) extend simple heaps with node tracking:

  • All simple heap operations
  • Push() returns a unique node ID
  • UpdateValue(id, newValue) - Update node value
  • UpdatePriority(id, newPriority) - Update node priority
  • Get(id), GetValue(id), GetPriority(id) - Retrieve by ID

📚 Usage

Non-Thread-Safe vs Thread-Safe

Each heap type has both non-thread-safe and thread-safe versions:

// Non-thread-safe version (faster, single-threaded use)
heap := heapcraft.NewDaryHeap[int](4, nil, func(a, b int) bool { 
    return a < b 
}, false)

// Thread-safe version (slower, concurrent use)
syncHeap := heapcraft.NewSyncDaryHeap[int](4, nil, func(a, b int) bool { 
    return a < b 
}, false)

D-ary Heaps

// Binary heap (2-ary) or D-ary heap with custom arity
heap := heapcraft.NewDaryHeap[int](4, nil, func(a, b int) bool { 
    return a < b 
}, false)

// Basic and advanced operations
heap.Push(1, 1)
heap.Update(0, 100, 10)
heap.PopPush(42, 5) 
value, _ := heap.PopValue()

Radix Heaps

// Radix heap for integer priorities
heap := heapcraft.NewRadixHeap[int, uint](nil, false)

// Operations (priorities must be >= last popped)
heap.Push(1, 1)
heap.Push(2, 2)
value, _ := heap.PopValue()
heap.Rebalance()

Regular Tree-Based Heaps

// Regular heap (Pairing, Skew, or Leftist)
heap := heapcraft.NewPairingHeap[int](nil, func(a, b int) bool { 
    return a < b 
}, false)

// Basic operations and merging
heap.Push(1, 1)
heap.Push(2, 2)
value, _ := heap.PopValue()
heap.MergeWith(otherHeap)

Full Tree-Based Heaps

// Full heap with node tracking
heap := heapcraft.NewFullPairingHeap[int](nil, func(a, b int) bool { 
    return a < b 
}, heapcraft.HeapConfig{UsePool: false})

// Node tracking operations
id := heap.Push(42, 10)
heap.UpdateValue(id, 100)
heap.UpdatePriority(id, 1)
value, _ := heap.GetValue(id)
heap.Remove(id)

Memory Pooling

Enable object pooling for better performance:

heap := heapcraft.NewDaryHeap[int](2, nil, func(a, b int) bool { 
    return a < b 
}, true)

Thread Safety

Use thread-safe versions for concurrent access:

// Thread-safe heap for concurrent use
syncHeap := heapcraft.NewSyncDaryHeap[int](nil, func(a, b int) bool { 
    return a < b 
}, false)

// Multiple goroutines can safely call these methods
go func() {
    syncHeap.Push(1, 1)
}()

go func() {
    value, err := syncHeap.PopValue()
}()

📈 Performance Benchmarks

Environment

Parameter Value
Date 2025-06-28
OS Windows 10
Architecture amd64
CPU AMD EPYC 7763 64-Core Processor
Go version 1.24

Micro-benchmark Highlights (pooling was not used in running these benchmarks to show raw timing)

D-ary and Radix Heaps
Heap Type Insertion Deletion PushPop PopPush
Iterations Time (ns/op) Iterations Time (ns/op) Iterations Time (ns/op) Iterations Time (ns/op)
BinaryHeap 19,454,936 52.71 3,510,987 374.7 3,807,219 393.9 3,662,504 392.8
DaryHeap (d=3) 32,970,384 42.15 4,658,214 284.4 3,828,266 398.7 3,718,894 391.9
DaryHeap (d=4) 38,662,906 26.42 5,091,660 259.8 3,833,235 400.1 3,725,020 401.0
RadixHeap 26,938,868 42.69 2,300,319 527.4 - - - -
Tree-based Heaps
Heap Type Insertion Deletion PushPop PopPush
Iterations Time (ns/op) Iterations Time (ns/op) Iterations Time (ns/op) Iterations Time (ns/op)
FullLeftistHeap 2,314,108 596.1 1,293,859 985.9 - - - -
LeftistHeap 9,481,090 130.8 1,891,108 772.2 - - - -
FullPairingHeap 2,569,038 469.5 4,440,087 338.8 - - - -
PairingHeap 25,685,535 44.34 11,306,653 123.5 - - - -
FullSkewHeap 1,000,000 1146 1,641,852 847.8 - - - -
SkewHeap 5,029,725 438.6 3,402,890 518.3 - - - -

Full Micro Benchmarks

BenchmarkBinaryHeapInsertion-4         	19454936	        52.71 ns/op	      83 B/op	       0 allocs/op
BenchmarkBinaryHeapDeletion-4          	 3510987	       374.7 ns/op	       0 B/op	       0 allocs/op
BenchmarkBinaryPushPop-4               	 3807219	       393.9 ns/op	       0 B/op	       0 allocs/op
BenchmarkBinaryPopPush-4               	 3662504	       392.8 ns/op	       0 B/op	       0 allocs/op
BenchmarkDaryHeap3Insertion-4          	32970384	        42.15 ns/op	      95 B/op	       0 allocs/op
BenchmarkDaryHeap3Deletion-4           	 4658214	       284.4 ns/op	       0 B/op	       0 allocs/op
BenchmarkDaryHeap3PushPop-4            	 3828266	       398.7 ns/op	       0 B/op	       0 allocs/op
BenchmarkDaryHeap3PopPush-4            	 3716894	       391.9 ns/op	       0 B/op	       0 allocs/op
BenchmarkDaryHeap4Insertion-4          	38662906	        26.42 ns/op	      81 B/op	       0 allocs/op
BenchmarkDaryHeap4Deletion-4           	 5091660	       259.8 ns/op	       0 B/op	       0 allocs/op
BenchmarkDaryHeap4PushPop-4            	 3833235	       400.1 ns/op	       0 B/op	       0 allocs/op
BenchmarkDaryHeap4PopPush-4            	 3725020	       401.0 ns/op	       0 B/op	       0 allocs/op
BenchmarkFullLeftistHeap_Insertion-4   	 2314108	       596.1 ns/op	     168 B/op	       2 allocs/op
BenchmarkFullLeftistHeap_Deletion-4    	 1293859	       985.9 ns/op	       0 B/op	       0 allocs/op
BenchmarkLeftistHeap_Insertion-4       	 9481090	       130.8 ns/op	      48 B/op	       1 allocs/op
BenchmarkLeftistHeap_Deletion-4        	 1891108	       772.2 ns/op	       0 B/op	       0 allocs/op
BenchmarkFullPairingHeap_Insertion-4   	 2569038	       469.5 ns/op	     158 B/op	       2 allocs/op
BenchmarkFullPairingHeap_Deletion-4    	 4440087	       338.8 ns/op	       0 B/op	       0 allocs/op
BenchmarkPairingHeap_Insertion-4       	25685535	        44.34 ns/op	      32 B/op	       1 allocs/op
BenchmarkPairingHeap_Deletion-4        	11306653	       123.5 ns/op	       0 B/op	       0 allocs/op
BenchmarkRadixHeapInsertion-4          	26938868	        42.69 ns/op	      70 B/op	       0 allocs/op
BenchmarkRadixHeapDeletion-4           	 2300319	       527.4 ns/op	     475 B/op	       3 allocs/op
BenchmarkFullSkewHeap_Insertion-4      	 1000000	      1146 ns/op	     239 B/op	       3 allocs/op
BenchmarkFullSkewHeap_Deletion-4       	 1641852	       847.8 ns/op	       0 B/op	       0 allocs/op
BenchmarkSkewHeap_Insertion-4          	 5029725	       438.6 ns/op	      32 B/op	       1 allocs/op
BenchmarkSkewHeap_Deletion-4           	 3402890	       518.3 ns/op	       0 B/op	       0 allocs/op

🤝 License

This project is licensed under the MIT License. See the LICENSE file for details.

📋 TODO

  • Interval Heap
  • Weak Heap
  • Enhanced Benchmarking
  • Pooling Benchmarks
  • Concurrency Testing

📞 Contact & Contributing

Feel free to open an issue or a pull request. Discussion and feedback are welcome!

Documentation

Index

Constants

This section is empty.

Variables

View Source 
var (
	// ErrCallbackNotFound is returned when attempting to deregister a callback that
	// doesn't exist.
	ErrCallbackNotFound = errors.New("callback not found")

	// ErrHeapEmpty is returned when attempting to access elements from an empty heap.
	ErrHeapEmpty = errors.New("the heap is empty and contains no elements")

	// ErrIndexOutOfBounds is returned when attempting to access an index that is outside
	// the valid range of the heap.
	ErrIndexOutOfBounds = errors.New("index out of bounds")

	// ErrPriorityLessThanLast is returned when attempting to insert a priority that is
	// less than the last extracted priority, which would violate the monotonic property
	// of the radix heap.
	ErrPriorityLessThanLast = errors.New("insertion of a priority less than last popped")

	// ErrNoRebalancingNeeded is returned when attempting to rebalance a radix heap
	// that doesn't need rebalancing (bucket 0 already contains elements).
	ErrNoRebalancingNeeded = errors.New("no rebalancing needed")

	// ErrNodeNotFound is returned when attempting to access a node with an ID that
	// does not exist in the pairing heap.
	ErrNodeNotFound = errors.New("id does not link to existing node")

	// ErrIDGenerationFailed is returned when attempting to generate a unique ID for a
	// node that already exists.
	ErrIDGenerationFailed = errors.New("failed to generate a unique ID")
)

Functions

func NewSyncCallbacks added in v0.2.0 

func NewSyncCallbacks() *syncCallbacks

NewSyncCallbacks creates a new thread-safe callbacks instance.

Types

type DaryHeap 

type DaryHeap[V any, P any] struct {
	// contains filtered or unexported fields
}

DaryHeap represents a generic d-ary heap with support for swap callbacks. The heap can be either a min-heap or max-heap depending on the comparison function. - data: slice of HeapNode containing value-priority pairs - cmp: comparison function that determines the heap order (min or max) - onSwap: callbacks invoked whenever two elements swap positions - d: the arity of the heap (e

func NLargestBinary 

func NLargestBinary[V any, P any](n int, data []HeapNode[V, P], lt func(a, b P) bool, usePool bool) *DaryHeap[V, P]

NLargestBinary returns a min-heap of size n containing the n largest elements from data, using a binary heap (d=2). The comparison function lt should return true if a < b. This is a convenience wrapper around NLargestDary.

func NLargestDary 

func NLargestDary[V any, P any](n int, d int, data []HeapNode[V, P], lt func(a, b P) bool, usePool bool) *DaryHeap[V, P]

NLargestDary returns a min-heap of size n containing the n largest elements from data. The comparison function lt should return true if a < b.

func NSmallestBinary 

func NSmallestBinary[V any, P any](n int, data []HeapNode[V, P], gt func(a, b P) bool, usePool bool) *DaryHeap[V, P]

NSmallestBinary returns a max-heap of size n containing the n smallest elements from data, using a binary heap (d=2). The comparison function gt should return true if a > b. This is a convenience wrapper around NSmallestDary.

func NSmallestDary 

func NSmallestDary[V any, P any](n int, d int, data []HeapNode[V, P], gt func(a, b P) bool, usePool bool) *DaryHeap[V, P]

NSmallestDary returns a max-heap of size n containing the n smallest elements from data. The comparison function gt should return true if a > b.

func NewBinaryHeap 

func NewBinaryHeap[V any, P any](data []HeapNode[V, P], cmp func(a, b P) bool, usePool bool) *DaryHeap[V, P]

NewBinaryHeap creates a new binary heap (d=2) from the given data slice and comparison function. The comparison function determines the heap order (min or max). It is a convenience wrapper around NewDaryHeap with d=2.

func NewBinaryHeapCopy 

func NewBinaryHeapCopy[V any, P any](data []HeapNode[V, P], cmp func(a, b P) bool, usePool bool) *DaryHeap[V, P]

NewBinaryHeapCopy creates a new binary heap (d=2) from a copy of the given data slice. Unlike NewBinaryHeap, this function creates a new slice and copies the data before heapifying it, leaving the original data unchanged. The comparison function determines the heap order (min or max). It is a convenience wrapper around NewDaryHeapCopy with d=2.

func NewDaryHeap 

func NewDaryHeap[V any, P any](d int, data []HeapNode[V, P], cmp func(a, b P) bool, usePool bool) *DaryHeap[V, P]

NewDaryHeap transforms the given slice of HeapNode into a valid d-ary heap in-place. The comparison function determines the heap order (min or max). Uses siftDown starting from the last parent toward the root to build the heap.

func NewDaryHeapCopy 

func NewDaryHeapCopy[V any, P any](d int, data []HeapNode[V, P], cmp func(a, b P) bool, usePool bool) *DaryHeap[V, P]

NewDaryHeapCopy creates a new d-ary heap from a copy of the provided data slice. The comparison function determines the heap order (min or max). The original data slice remains unchanged.

func (*DaryHeap[V, P]) Clear 

func (h *DaryHeap[V, P]) Clear()

Clear removes all elements from the heap by resetting its underlying slice to length zero.

func (*DaryHeap[V, P]) Clone 

func (h *DaryHeap[V, P]) Clone() *DaryHeap[V, P]

Clone creates a deep copy of the heap structure. The new heap preserves the original size. If values or priorities are reference types, those reference values are shared between the original and cloned heaps.

func (*DaryHeap[V, P]) Deregister 

func (h *DaryHeap[V, P]) Deregister(id string) error

Deregister removes the callback with the specified ID from the heap's swap callbacks. Returns an error if no callback exists with the given ID.

func (*DaryHeap[V, P]) IsEmpty 

func (h *DaryHeap[V, P]) IsEmpty() bool

IsEmpty returns true if the heap contains no elements.

func (*DaryHeap[V, P]) Length 

func (h *DaryHeap[V, P]) Length() int

Length returns the current number of elements in the heap.

func (*DaryHeap[V, P]) Peek 

func (h *DaryHeap[V, P]) Peek() (V, P, error)

Peek returns the root HeapNode without removing it. If the heap is empty, returns a zero value and priority with an error.

func (*DaryHeap[V, P]) PeekPriority 

func (h *DaryHeap[V, P]) PeekPriority() (P, error)

PeekPriority returns just the priority of the root element without removing it. If the heap is empty, returns a zero value with an error.

func (*DaryHeap[V, P]) PeekValue 

func (h *DaryHeap[V, P]) PeekValue() (V, error)

PeekValue returns just the value of the root element without removing it. If the heap is empty, returns a zero value with an error.

func (*DaryHeap[V, P]) Pop 

func (h *DaryHeap[V, P]) Pop() (V, P, error)

Pop removes and returns the root element of the heap (minimum or maximum per cmp). If the heap is empty, returns a zero value and priority with an error.

func (*DaryHeap[V, P]) PopPriority 

func (h *DaryHeap[V, P]) PopPriority() (P, error)

PopPriority removes and returns just the priority of the root element. If the heap is empty, returns a zero value with an error.

func (*DaryHeap[V, P]) PopPush 

func (h *DaryHeap[V, P]) PopPush(value V, priority P) (V, P)

PopPush atomically removes the root element and inserts a new element into the heap. Returns the removed root element.

func (*DaryHeap[V, P]) PopValue 

func (h *DaryHeap[V, P]) PopValue() (V, error)

PopValue removes and returns just the value of the root element. If the heap is empty, returns a zero value with an error.

func (*DaryHeap[V, P]) Push 

func (h *DaryHeap[V, P]) Push(value V, priority P)

Push inserts a new element with the given value and priority into the heap. The element is added at the end and then sifted up to maintain the heap property.

func (*DaryHeap[V, P]) PushPop 

func (h *DaryHeap[V, P]) PushPop(value V, priority P) (V, P)

PushPop atomically inserts a new element and removes the root element if the new element doesn't belong at the root. If the new element belongs at the root, it is returned directly. Returns either the new element or the old root element.

func (*DaryHeap[V, P]) Register 

func (h *DaryHeap[V, P]) Register(fn func(x, y int)) callback

Register adds a callback function to be called whenever elements in the heap swap positions. Returns a callback that can be used to deregister the function later.

func (*DaryHeap[V, P]) Remove 

func (h *DaryHeap[V, P]) Remove(i int) (V, P, error)

Remove deletes the element at index i from the heap and returns it. The heap property is restored by replacing the removed element with the last element and sifting it down to its appropriate position. Returns the removed element and an error if the index is out of bounds.

func (*DaryHeap[V, P]) Update 

func (h *DaryHeap[V, P]) Update(i int, value V, priority P) error

Update replaces the element at index i with a new value and priority. It then restores the heap property by either sifting up (if the new priority is more appropriate than its parent) or sifting down (if the new priority is less appropriate than its children). Returns an error if the index is out of bounds.

type FullLeftistHeap added in v0.2.0 

type FullLeftistHeap[V any, P any] struct {
	// contains filtered or unexported fields
}

FullLeftistHeap implements a leftist heap with node tracking capabilities. Maintains a map of node IDs to nodes for O(1) access and updates. The heap property is maintained through the comparison function.

func NewFullLeftistHeap added in v0.2.0 

func NewFullLeftistHeap[V any, P any](data []HeapNode[V, P], cmp func(a, b P) bool, config HeapConfig) *FullLeftistHeap[V, P]

NewLeftistHeap constructs a leftist heap with node tracking from a slice of HeapPairs. Each node is assigned a unique ID and stored in a map for O(1) access. Uses a queue to iteratively merge singleton nodes until one root remains. The comparison function determines the heap order (min or max).

func (*FullLeftistHeap[V, P]) Clear added in v0.2.0 

func (l *FullLeftistHeap[V, P]) Clear()

Clear removes all elements from the heap and resets its state. The heap is ready for new insertions after clearing.

func (*FullLeftistHeap[V, P]) Clone added in v0.2.0 

func (l *FullLeftistHeap[V, P]) Clone() *FullLeftistHeap[V, P]

Clone creates a deep copy of the heap structure and nodes. If values or priorities are reference types, those reference values are shared between the original and cloned heaps.

func (*FullLeftistHeap[V, P]) Get added in v0.2.0 

func (l *FullLeftistHeap[V, P]) Get(id string) (V, P, error)

Get returns the element associated with the given ID. Returns an error if the ID doesn't exist in the heap.

func (*FullLeftistHeap[V, P]) GetPriority added in v0.2.0 

func (l *FullLeftistHeap[V, P]) GetPriority(id string) (P, error)

GetPriority returns the priority associated with the given ID. Returns zero value and an error if the ID doesn't exist in the heap.

func (*FullLeftistHeap[V, P]) GetValue added in v0.2.0 

func (l *FullLeftistHeap[V, P]) GetValue(id string) (V, error)

GetValue returns the value associated with the given ID. Returns zero value and an error if the ID doesn't exist in the heap.

func (*FullLeftistHeap[V, P]) IsEmpty added in v0.2.0 

func (l *FullLeftistHeap[V, P]) IsEmpty() bool

IsEmpty returns true if the heap contains no elements.

func (*FullLeftistHeap[V, P]) Length added in v0.2.0 

func (l *FullLeftistHeap[V, P]) Length() int

Length returns the current number of elements in the heap.

func (*FullLeftistHeap[V, P]) Peek added in v0.2.0 

func (l *FullLeftistHeap[V, P]) Peek() (V, P, error)

Peek returns the minimum element without removing it. Returns nil and an error if the heap is empty.

func (*FullLeftistHeap[V, P]) PeekPriority added in v0.2.0 

func (l *FullLeftistHeap[V, P]) PeekPriority() (P, error)

PeekPriority returns the priority at the root without removing it. Returns zero value and an error if the heap is empty.

func (*FullLeftistHeap[V, P]) PeekValue added in v0.2.0 

func (l *FullLeftistHeap[V, P]) PeekValue() (V, error)

PeekValue returns the value at the root without removing it. Returns zero value and an error if the heap is empty.

func (*FullLeftistHeap[V, P]) Pop added in v0.2.0 

func (l *FullLeftistHeap[V, P]) Pop() (V, P, error)

Pop removes and returns the minimum element from the heap. The heap property is restored through merging the root's children. Returns nil and an error if the heap is empty.

func (*FullLeftistHeap[V, P]) PopPriority added in v0.2.0 

func (l *FullLeftistHeap[V, P]) PopPriority() (P, error)

PopPriority removes and returns just the priority at the root. The heap property is restored through merging the root's children. Returns zero value and an error if the heap is empty.

func (*FullLeftistHeap[V, P]) PopValue added in v0.2.0 

func (l *FullLeftistHeap[V, P]) PopValue() (V, error)

PopValue removes and returns just the value at the root. The heap property is restored through merging the root's children. Returns zero value and an error if the heap is empty.

func (*FullLeftistHeap[V, P]) Push added in v0.2.0 

func (l *FullLeftistHeap[V, P]) Push(value V, priority P) (string, error)

Push adds a new element to the heap by creating a singleton node and merging it with the existing tree. The new node is assigned a unique ID and stored in the elements map. Returns the ID of the inserted node.

func (*FullLeftistHeap[V, P]) UpdatePriority added in v0.2.0 

func (l *FullLeftistHeap[V, P]) UpdatePriority(id string, priority P) error

UpdatePriority changes the priority of the node with the given ID and restructures the heap to maintain the heap property. Returns an error if the ID doesn't exist in the heap.

func (*FullLeftistHeap[V, P]) UpdateValue added in v0.2.0 

func (l *FullLeftistHeap[V, P]) UpdateValue(id string, value V) error

UpdateValue changes the value of the node with the given ID. Returns an error if the ID doesn't exist in the heap.

type FullPairingHeap added in v0.2.0 

type FullPairingHeap[V any, P any] struct {
	// contains filtered or unexported fields
}

FullPairingHeap implements a pairing heap data structure with node tracking. It maintains a multi-way tree structure where each node can have multiple children. The heap supports efficient insertion, deletion, and priority updates of nodes. Nodes are tracked by unique IDs, allowing for O(1) access and updates.

func NewFullPairingHeap added in v0.2.0 

func NewFullPairingHeap[V any, P any](data []HeapNode[V, P], cmp func(a, b P) bool, config HeapConfig) *FullPairingHeap[V, P]

NewFullPairingHeap creates a new pairing heap from a slice of HeapPairs. The heap is initialized with the provided elements and uses the given comparison function to determine heap order. The comparison function determines the heap order (min or max). Returns an empty heap if the input slice is empty.

func (*FullPairingHeap[V, P]) Clear added in v0.2.0 

func (p *FullPairingHeap[V, P]) Clear()

Clear removes all elements from the heap. Resets the root to nil, size to zero, and initializes a new empty element map. The next node ID is reset to 1.

func (*FullPairingHeap[V, P]) Clone added in v0.2.0 

func (p *FullPairingHeap[V, P]) Clone() *FullPairingHeap[V, P]

Clone creates a deep copy of the heap structure and nodes. If values or priorities are reference types, those reference values are shared between the original and cloned heaps.

func (*FullPairingHeap[V, P]) Get added in v0.2.0 

func (p *FullPairingHeap[V, P]) Get(id string) (V, P, error)

Get retrieves a HeapNode for the node with the given ID. Returns an error if the ID does not exist in the heap.

func (*FullPairingHeap[V, P]) GetPriority added in v0.2.0 

func (p *FullPairingHeap[V, P]) GetPriority(id string) (P, error)

GetPriority retrieves the priority of the node with the given ID. Returns zero value and an error if the ID does not exist in the heap.

func (*FullPairingHeap[V, P]) GetValue added in v0.2.0 

func (p *FullPairingHeap[V, P]) GetValue(id string) (V, error)

GetValue retrieves the value of the node with the given ID. Returns zero value and an error if the ID does not exist in the heap.

func (*FullPairingHeap[V, P]) IsEmpty added in v0.2.0 

func (p *FullPairingHeap[V, P]) IsEmpty() bool

IsEmpty returns true if the heap contains no elements.

func (*FullPairingHeap[V, P]) Length added in v0.2.0 

func (p *FullPairingHeap[V, P]) Length() int

Length returns the current number of elements in the heap.

func (*FullPairingHeap[V, P]) Peek added in v0.2.0 

func (p *FullPairingHeap[V, P]) Peek() (V, P, error)

Peek returns a HeapNode containing the value and priority of the root node without removing it. Returns nil and an error if the heap is empty.

func (*FullPairingHeap[V, P]) PeekPriority added in v0.2.0 

func (p *FullPairingHeap[V, P]) PeekPriority() (P, error)

PeekPriority returns the priority at the root without removing it. Returns zero value and an error if the heap is empty.

func (*FullPairingHeap[V, P]) PeekValue added in v0.2.0 

func (p *FullPairingHeap[V, P]) PeekValue() (V, error)

PeekValue returns the value at the root without removing it. Returns zero value and an error if the heap is empty.

func (*FullPairingHeap[V, P]) Pop added in v0.2.0 

func (p *FullPairingHeap[V, P]) Pop() (V, P, error)

Pop removes and returns a HeapNode containing the value and priority of the root node. The root's children are merged to form the new heap. Returns nil and an error if the heap is empty.

func (*FullPairingHeap[V, P]) PopPriority added in v0.2.0 

func (p *FullPairingHeap[V, P]) PopPriority() (P, error)

PopPriority removes and returns just the priority at the root. The root's children are merged to form the new heap. Returns zero value and an error if the heap is empty.

func (*FullPairingHeap[V, P]) PopValue added in v0.2.0 

func (p *FullPairingHeap[V, P]) PopValue() (V, error)

PopValue removes and returns just the value at the root. The root's children are merged to form the new heap. Returns zero value and an error if the heap is empty.

func (*FullPairingHeap[V, P]) Push added in v0.2.0 

func (p *FullPairingHeap[V, P]) Push(value V, priority P) (string, error)

Push adds a new element with the given value and priority to the heap. A new node is created with a unique ID and melded with the existing root. The new node becomes the root if its priority is higher than the current root's. Returns the ID of the inserted node.

func (*FullPairingHeap[V, P]) UpdatePriority added in v0.2.0 

func (p *FullPairingHeap[V, P]) UpdatePriority(id string, priority P) error

UpdatePriority updates the priority of a node with the given ID. Returns an error if the ID does not exist in the heap. The node is removed from its current position and reinserted into the heap to maintain the heap property. This operation may change the heap structure.

func (*FullPairingHeap[V, P]) UpdateValue added in v0.2.0 

func (p *FullPairingHeap[V, P]) UpdateValue(id string, value V) error

UpdateValue updates the value of a node with the given ID. Returns an error if the ID does not exist in the heap. The heap structure remains unchanged as this operation only modifies the value.

type FullSkewHeap added in v0.2.0 

type FullSkewHeap[V any, P any] struct {
	// contains filtered or unexported fields
}

FullSkewHeap implements a skew heap with parent pointers and element tracking. It maintains a map of node IDs to nodes for O(1) element access and updates. The heap can be either a min-heap or max-heap depending on the comparison function.

func NewFullSkewHeap added in v0.2.0 

func NewFullSkewHeap[V any, P any](data []HeapNode[V, P], cmp func(a, b P) bool, config HeapConfig) *FullSkewHeap[V, P]

NewFullSkewHeap creates a new skew heap from the given data slice. Each element is inserted individually using the provided comparison function to determine heap order (min or max). Returns an empty heap if the input slice is empty.

func (*FullSkewHeap[V, P]) Clear added in v0.2.0 

func (s *FullSkewHeap[V, P]) Clear()

Clear removes all elements from the heap. Resets the root to nil, size to zero, and initializes a new empty element map. The next node ID is reset to 1.

func (*FullSkewHeap[V, P]) Clone added in v0.2.0 

func (s *FullSkewHeap[V, P]) Clone() *FullSkewHeap[V, P]

Clone creates a deep copy of the heap structure and nodes. If values or priorities are reference types, those reference values are shared between the original and cloned heaps.

func (*FullSkewHeap[V, P]) Get added in v0.2.0 

func (s *FullSkewHeap[V, P]) Get(id string) (V, P, error)

Get returns the element with the given ID. Returns nil and an error if the ID does not exist.

func (*FullSkewHeap[V, P]) GetPriority added in v0.2.0 

func (s *FullSkewHeap[V, P]) GetPriority(id string) (P, error)

GetPriority returns the priority of the element with the given ID. Returns zero value and an error if the ID does not exist.

func (*FullSkewHeap[V, P]) GetValue added in v0.2.0 

func (s *FullSkewHeap[V, P]) GetValue(id string) (V, error)

GetValue returns the value of the element with the given ID. Returns zero value and an error if the ID does not exist.

func (*FullSkewHeap[V, P]) IsEmpty added in v0.2.0 

func (s *FullSkewHeap[V, P]) IsEmpty() bool

IsEmpty returns true if the heap contains no elements.

func (*FullSkewHeap[V, P]) Length added in v0.2.0 

func (s *FullSkewHeap[V, P]) Length() int

Length returns the current number of elements in the heap.

func (*FullSkewHeap[V, P]) Peek added in v0.2.0 

func (s *FullSkewHeap[V, P]) Peek() (V, P, error)

Peek returns the minimum element without removing it. Returns nil and an error if the heap is empty.

func (*FullSkewHeap[V, P]) PeekPriority added in v0.2.0 

func (s *FullSkewHeap[V, P]) PeekPriority() (P, error)

PeekPriority returns the priority of the minimum element without removing it. Returns zero value and an error if the heap is empty.

func (*FullSkewHeap[V, P]) PeekValue added in v0.2.0 

func (s *FullSkewHeap[V, P]) PeekValue() (V, error)

PeekValue returns the value of the minimum element without removing it. Returns zero value and an error if the heap is empty.

func (*FullSkewHeap[V, P]) Pop added in v0.2.0 

func (s *FullSkewHeap[V, P]) Pop() (V, P, error)

Pop removes and returns the minimum element from the heap. Returns nil and an error if the heap is empty.

func (*FullSkewHeap[V, P]) PopPriority added in v0.2.0 

func (s *FullSkewHeap[V, P]) PopPriority() (P, error)

PopPriority removes and returns the priority of the minimum element. Returns zero value and an error if the heap is empty.

func (*FullSkewHeap[V, P]) PopValue added in v0.2.0 

func (s *FullSkewHeap[V, P]) PopValue() (V, error)

PopValue removes and returns the value of the minimum element. Returns zero value and an error if the heap is empty.

func (*FullSkewHeap[V, P]) Push added in v0.2.0 

func (s *FullSkewHeap[V, P]) Push(value V, priority P) (string, error)

Push adds a new element to the heap. The element is assigned a unique ID and stored in the elements map. Returns the ID of the inserted node.

func (*FullSkewHeap[V, P]) UpdatePriority added in v0.2.0 

func (s *FullSkewHeap[V, P]) UpdatePriority(id string, priority P) error

UpdatePriority updates the priority of the element with the given ID. The heap is restructured to maintain the heap property. Returns an error if the ID does not exist.

func (*FullSkewHeap[V, P]) UpdateValue added in v0.2.0 

func (s *FullSkewHeap[V, P]) UpdateValue(id string, value V) error

UpdateValue updates the value of the element with the given ID. Returns an error if the ID does not exist. The heap structure remains unchanged as this operation only modifies the value.

type HeapConfig added in v0.2.0 

type HeapConfig struct {
	// UsePool is a boolean that indicates whether to use a pool for the heap.
	UsePool bool
	// IDGenerator is a pointer to an IDGenerator that is used to generate
	// unique IDs for the heap. If nil, the default IDGenerator is used.
	IDGenerator IDGenerator
}

HeapConfig is a struct that contains the configuration for a heap.

func (*HeapConfig) GetGenerator added in v0.2.0 

func (h *HeapConfig) GetGenerator() IDGenerator

GetGenerator returns the IDGenerator from the HeapConfig. If the IDGenerator is nil, the default IDGenerator is returned.

type HeapNode 

type HeapNode[V any, P any] struct {
	// contains filtered or unexported fields
}

HeapNode binds a value to its priority for heap operations.

func CreateHeapNode 

func CreateHeapNode[V any, P any](value V, priority P) HeapNode[V, P]

CreateHeapNode constructs a new HeapNode from the given value and priority.

type IDGenerator added in v0.2.0 

type IDGenerator interface{ Next() string }

IDGenerator is an interface that details a structure that can generate unique IDs.

type IntegerIDGenerator added in v0.2.0 

type IntegerIDGenerator struct{ NextID int }

IntegerIDGenerator is a generator that uses integers.

func (*IntegerIDGenerator) Next added in v0.2.0 

func (g *IntegerIDGenerator) Next() string

Next returns the next integer ID as a string.

type LeftistHeap 

type LeftistHeap[V any, P any] struct {
	// contains filtered or unexported fields
}

LeftistHeap implements a basic leftist heap without node tracking. Maintains the heap property through the comparison function and the leftist property through s-values.

func NewLeftistHeap 

func NewLeftistHeap[V any, P any](data []HeapNode[V, P], cmp func(a, b P) bool, usePool bool) *LeftistHeap[V, P]

NewLeftistHeap constructs a leftist heap from a slice of HeapPairs. Uses a queue to iteratively merge singleton nodes until one root remains. The comparison function determines the heap order (min or max).

func (*LeftistHeap[V, P]) Clear 

func (l *LeftistHeap[V, P]) Clear()

Clear removes all elements from the simple heap. The heap is ready for new insertions after clearing.

func (*LeftistHeap[V, P]) Clone 

func (l *LeftistHeap[V, P]) Clone() *LeftistHeap[V, P]

Clone creates a deep copy of the heap structure and nodes. If values or priorities are reference types, those reference values are shared between the original and cloned heaps.

func (*LeftistHeap[V, P]) IsEmpty 

func (l *LeftistHeap[V, P]) IsEmpty() bool

IsEmpty returns true if the simple heap contains no elements.

func (*LeftistHeap[V, P]) Length 

func (l *LeftistHeap[V, P]) Length() int

Length returns the current number of elements in the simple heap.

func (*LeftistHeap[V, P]) Peek 

func (l *LeftistHeap[V, P]) Peek() (V, P, error)

Peek returns the minimum element without removing it. Returns nil and an error if the heap is empty.

func (*LeftistHeap[V, P]) PeekPriority 

func (l *LeftistHeap[V, P]) PeekPriority() (P, error)

PeekPriority returns the priority at the root without removing it. Returns zero value and an error if the heap is empty.

func (*LeftistHeap[V, P]) PeekValue 

func (l *LeftistHeap[V, P]) PeekValue() (V, error)

PeekValue returns the value at the root without removing it. Returns zero value and an error if the heap is empty.

func (*LeftistHeap[V, P]) Pop 

func (l *LeftistHeap[V, P]) Pop() (V, P, error)

Pop removes and returns the minimum element from the simple heap. The heap property is restored through merging the root's children. Returns nil and an error if the heap is empty.

func (*LeftistHeap[V, P]) PopPriority 

func (l *LeftistHeap[V, P]) PopPriority() (P, error)

PopPriority removes and returns just the priority at the root. The heap property is restored through merging the root's children. Returns zero value and an error if the heap is empty.

func (*LeftistHeap[V, P]) PopValue 

func (l *LeftistHeap[V, P]) PopValue() (V, error)

PopValue removes and returns just the value at the root. The heap property is restored through merging the root's children. Returns zero value and an error if the heap is empty.

func (*LeftistHeap[V, P]) Push 

func (l *LeftistHeap[V, P]) Push(value V, priority P)

Push adds a new element to the simple heap by creating a singleton node and merging it with the existing tree.

type PairingHeap 

type PairingHeap[V any, P any] struct {
	// contains filtered or unexported fields
}

PairingHeap implements a basic pairing heap without node tracking. It maintains a multi-way tree structure but does not support node updates or removal of arbitrary nodes. This implementation is simpler but less feature-rich than FullPairingHeap.

func NewPairingHeap 

func NewPairingHeap[V any, P any](data []HeapNode[V, P], cmp func(a, b P) bool, usePool bool) *PairingHeap[V, P]

NewPairingHeap creates a new simple pairing heap from a slice of HeapPairs. Unlike PairingHeap, this implementation does not track node IDs or support node updates. It uses the provided comparison function to determine heap order (min or max). Returns an empty heap if the input slice is empty.

func (*PairingHeap[V, P]) Clear 

func (p *PairingHeap[V, P]) Clear()

Clear removes all elements from the simple heap. The heap is ready for new insertions after clearing.

func (*PairingHeap[V, P]) Clone 

func (p *PairingHeap[V, P]) Clone() *PairingHeap[V, P]

Clone creates a deep copy of the heap structure and nodes. If values or priorities are reference types, those reference values are shared between the original and cloned heaps.

func (*PairingHeap[V, P]) IsEmpty 

func (p *PairingHeap[V, P]) IsEmpty() bool

IsEmpty returns true if the simple heap contains no elements.

func (*PairingHeap[V, P]) Length 

func (p *PairingHeap[V, P]) Length() int

Length returns the current number of elements in the heap.

func (*PairingHeap[V, P]) Peek 

func (p *PairingHeap[V, P]) Peek() (V, P, error)

Peek returns a HeapNode containing the value and priority of the root node without removing it. Returns nil and an error if the heap is empty.

func (*PairingHeap[V, P]) PeekPriority 

func (p *PairingHeap[V, P]) PeekPriority() (P, error)

PeekPriority returns the priority at the root without removing it. Returns zero value and an error if the heap is empty.

func (*PairingHeap[V, P]) PeekValue 

func (p *PairingHeap[V, P]) PeekValue() (V, error)

PeekValue returns the value at the root without removing it. Returns zero value and an error if the heap is empty.

func (*PairingHeap[V, P]) Pop 

func (p *PairingHeap[V, P]) Pop() (V, P, error)

Pop removes and returns a HeapNode containing the value and priority of the root node. The root's children are merged to form the new heap. Returns nil and an error if the heap is empty.

func (*PairingHeap[V, P]) PopPriority 

func (p *PairingHeap[V, P]) PopPriority() (P, error)

PopPriority removes and returns just the priority at the root. The root's children are merged to form the new heap. Returns zero value and an error if the heap is empty.

func (*PairingHeap[V, P]) PopValue 

func (p *PairingHeap[V, P]) PopValue() (V, error)

PopValue removes and returns just the value at the root. The root's children are merged to form the new heap. Returns zero value and an error if the heap is empty.

func (*PairingHeap[V, P]) Push 

func (p *PairingHeap[V, P]) Push(value V, priority P)

Push adds a new element with its priority by creating a single-node heap and melding it with the existing root. The new node becomes the root if its priority is higher than the current root's priority.

type RadixHeap 

type RadixHeap[V any, P constraints.Unsigned] struct {
	// contains filtered or unexported fields
}

RadixHeap implements a monotonic priority queue over unsigned priorities. The heap maintains the invariant that priorities must be non-decreasing.

  • buckets: array of slices of HeapNode, each holding items whose priorities fall within a range defined by 'last'.
  • size: the count of elements in the heap.
  • last: the most recently extracted minimum priority.

func NewRadixHeap 

func NewRadixHeap[V any, P constraints.Unsigned](data []HeapNode[V, P], usePool bool) *RadixHeap[V, P]

NewRadixHeap creates a RadixHeap from a given slice of HeapNode[V,P]. It determines the number of buckets from the bit-length of P, initializess 'last' to the minimum priority if data is present, and assigns each element into its corresponding bucket. The heap maintains a monotonic property where priorities must be non-decreasing.

func (*RadixHeap[V, P]) Clear 

func (r *RadixHeap[V, P]) Clear()

Clear reinitializes the heap by creating fresh buckets, resetting size to zero, and setting 'last' back to its zero value.

func (*RadixHeap[V, P]) Clone 

func (r *RadixHeap[V, P]) Clone() *RadixHeap[V, P]

Clone creates a deep copy of the heap structure. The new heap preserves the original size and last value. If values or priorities are reference types, those reference values are shared between the original and cloned heaps.

func (*RadixHeap[V, P]) IsEmpty 

func (r *RadixHeap[V, P]) IsEmpty() bool

IsEmpty returns true if the heap contains no items.

func (*RadixHeap[V, P]) Length 

func (r *RadixHeap[V, P]) Length() int

Length returns the number of items currently stored in the heap.

func (*RadixHeap[V, P]) Merge 

func (r *RadixHeap[V, P]) Merge(radix *RadixHeap[V, P])

Merge integrates another RadixHeap into this one. It selects the heap with the smaller 'last' as the new baseline, adopts its buckets and 'last', then reinserts all items from the other heap to preserve the monotonic property.

func (*RadixHeap[V, P]) Peek 

func (r *RadixHeap[V, P]) Peek() (V, P, error)

Peek returns a HeapNode with the minimum priority without removing it. Returns nil and an error if the heap is empty.

func (*RadixHeap[V, P]) PeekPriority 

func (r *RadixHeap[V, P]) PeekPriority() (P, error)

PeekPriority returns just the priority of the root element without removing it. Returns zero value and an error if the heap is empty.

func (*RadixHeap[V, P]) PeekValue 

func (r *RadixHeap[V, P]) PeekValue() (V, error)

PeekValue returns just the value of the root element without removing it. Returns zero value and an error if the heap is empty.

func (*RadixHeap[V, P]) Pop 

func (r *RadixHeap[V, P]) Pop() (V, P, error)

Pop extracts and returns the HeapNode with the minimum priority. Returns nil and an error if the heap is empty.

func (*RadixHeap[V, P]) PopPriority 

func (r *RadixHeap[V, P]) PopPriority() (P, error)

PopPriority removes and returns just the priority of the root element. Returns zero value and an error if the heap is empty.

func (*RadixHeap[V, P]) PopValue 

func (r *RadixHeap[V, P]) PopValue() (V, error)

PopValue removes and returns just the value of the root element. Returns zero value and an error if the heap is empty.

func (*RadixHeap[V, P]) Push 

func (r *RadixHeap[V, P]) Push(value V, priority P) error

Push adds a new value and priority pair into the heap. Returns an error if the priority is less than r.last, as this would violate the monotonic property. Otherwise, puts the item into the appropriate bucket and increments the size.

func (*RadixHeap[V, P]) Rebalance 

func (r *RadixHeap[V, P]) Rebalance() error

Rebalance fills bucket 0 if it is empty. Returns an error if the heap is empty, or if bucket 0 already contains elements (no action was needed).

type SkewHeap 

type SkewHeap[V any, P any] struct {
	// contains filtered or unexported fields
}

SkewHeap implements a basic skew heap without parent pointers. It provides the same core functionality as FullSkewHeap but without element tracking. The heap can be either a min-heap or max-heap depending on the comparison function.

func NewSkewHeap 

func NewSkewHeap[V any, P any](data []HeapNode[V, P], cmp func(a, b P) bool, usePool bool) *SkewHeap[V, P]

NewSkewHeap creates a new simple skew heap from the given data slice. Each element is inserted individually using the provided comparison function to determine heap order (min or max). Returns an empty heap if the input slice is empty.

func (*SkewHeap[V, P]) Clear 

func (s *SkewHeap[V, P]) Clear()

Clear removes all elements from the heap. Resets the root to nil and size to zero.

func (*SkewHeap[V, P]) Clone 

func (s *SkewHeap[V, P]) Clone() *SkewHeap[V, P]

Clone creates a deep copy of the heap structure and nodes. If values or priorities are reference types, those reference values are shared between the original and cloned heaps.

func (*SkewHeap[V, P]) IsEmpty 

func (s *SkewHeap[V, P]) IsEmpty() bool

IsEmpty returns true if the heap contains no elements.

func (*SkewHeap[V, P]) Length 

func (s *SkewHeap[V, P]) Length() int

Length returns the current number of elements in the heap.

func (*SkewHeap[V, P]) Peek 

func (s *SkewHeap[V, P]) Peek() (V, P, error)

Peek returns the minimum element without removing it. Returns nil and an error if the heap is empty.

func (*SkewHeap[V, P]) PeekPriority 

func (s *SkewHeap[V, P]) PeekPriority() (P, error)

PeekPriority returns the priority of the minimum element without removing it. Returns zero value and an error if the heap is empty.

func (*SkewHeap[V, P]) PeekValue 

func (s *SkewHeap[V, P]) PeekValue() (V, error)

PeekValue returns the value of the minimum element without removing it. Returns zero value and an error if the heap is empty.

func (*SkewHeap[V, P]) Pop 

func (s *SkewHeap[V, P]) Pop() (V, P, error)

Pop removes and returns the minimum element from the heap. Returns nil and an error if the heap is empty.

func (*SkewHeap[V, P]) PopPriority 

func (s *SkewHeap[V, P]) PopPriority() (P, error)

PopPriority removes and returns the priority of the minimum element. Returns zero value and an error if the heap is empty.

func (*SkewHeap[V, P]) PopValue 

func (s *SkewHeap[V, P]) PopValue() (V, error)

PopValue removes and returns the value of the minimum element. Returns zero value and an error if the heap is empty.

func (*SkewHeap[V, P]) Push 

func (s *SkewHeap[V, P]) Push(value V, priority P)

Push adds a new element to the heap. The element is merged with the existing root to maintain the heap property.

type SyncDaryHeap added in v0.2.0 

type SyncDaryHeap[V any, P any] struct {
	// contains filtered or unexported fields
}

SyncDaryHeap represents a thread-safe wrapper around DaryHeap. It provides the same interface as DaryHeap but with mutex-protected operations.

func NewSyncBinaryHeap added in v0.2.0 

func NewSyncBinaryHeap[V any, P any](data []HeapNode[V, P], cmp func(a, b P) bool, usePool bool) *SyncDaryHeap[V, P]

NewSyncBinaryHeap creates a new thread-safe binary heap (d=2) from the given data slice and comparison function. The comparison function determines the heap order (min or max).

func NewSyncBinaryHeapCopy added in v0.2.0 

func NewSyncBinaryHeapCopy[V any, P any](data []HeapNode[V, P], cmp func(a, b P) bool, usePool bool) *SyncDaryHeap[V, P]

NewSyncBinaryHeapCopy creates a new thread-safe binary heap (d=2) from a copy of the given data slice. Unlike NewSyncBinaryHeap, this function creates a new slice and copies the data before heapifying it, leaving the original data unchanged.

func NewSyncDaryHeap added in v0.2.0 

func NewSyncDaryHeap[V any, P any](d int, data []HeapNode[V, P], cmp func(a, b P) bool, usePool bool) *SyncDaryHeap[V, P]

NewSyncDaryHeap creates a new thread-safe d-ary heap from the given data slice and comparison function. The comparison function determines the heap order (min or max).

func NewSyncDaryHeapCopy added in v0.2.0 

func NewSyncDaryHeapCopy[V any, P any](d int, data []HeapNode[V, P], cmp func(a, b P) bool, usePool bool) *SyncDaryHeap[V, P]

NewSyncDaryHeapCopy creates a new thread-safe d-ary heap from a copy of the provided data slice. The comparison function determines the heap order (min or max). The original data slice remains unchanged.

func (*SyncDaryHeap[V, P]) Clear added in v0.2.0 

func (h *SyncDaryHeap[V, P]) Clear()

Clear removes all elements from the heap by resetting its underlying slice to length zero.

func (*SyncDaryHeap[V, P]) Clone added in v0.2.0 

func (h *SyncDaryHeap[V, P]) Clone() *SyncDaryHeap[V, P]

Clone creates a deep copy of the heap structure. The new heap preserves the original size. If values or priorities are reference types, those reference values are shared between the original and cloned heaps.

func (*SyncDaryHeap[V, P]) Deregister added in v0.2.0 

func (h *SyncDaryHeap[V, P]) Deregister(id string) error

Deregister removes the callback with the specified ID from the heap's swap callbacks. Returns an error if no callback exists with the given ID.

func (*SyncDaryHeap[V, P]) IsEmpty added in v0.2.0 

func (h *SyncDaryHeap[V, P]) IsEmpty() bool

IsEmpty returns true if the heap contains no elements.

func (*SyncDaryHeap[V, P]) Length added in v0.2.0 

func (h *SyncDaryHeap[V, P]) Length() int

Length returns the current number of elements in the heap.

func (*SyncDaryHeap[V, P]) Peek added in v0.2.0 

func (h *SyncDaryHeap[V, P]) Peek() (V, P, error)

Peek returns the root HeapNode without removing it. If the heap is empty, returns a zero value and priority with an error.

func (*SyncDaryHeap[V, P]) PeekPriority added in v0.2.0 

func (h *SyncDaryHeap[V, P]) PeekPriority() (P, error)

PeekPriority returns just the priority of the root element without removing it. If the heap is empty, returns a zero value with an error.

func (*SyncDaryHeap[V, P]) PeekValue added in v0.2.0 

func (h *SyncDaryHeap[V, P]) PeekValue() (V, error)

PeekValue returns just the value of the root element without removing it. If the heap is empty, returns a zero value with an error.

func (*SyncDaryHeap[V, P]) Pop added in v0.2.0 

func (h *SyncDaryHeap[V, P]) Pop() (V, P, error)

Pop removes and returns the root element of the heap (minimum or maximum per cmp). If the heap is empty, returns a zero value and priority with an error.

func (*SyncDaryHeap[V, P]) PopPriority added in v0.2.0 

func (h *SyncDaryHeap[V, P]) PopPriority() (P, error)

PopPriority removes and returns just the priority of the root element. If the heap is empty, returns a zero value with an error.

func (*SyncDaryHeap[V, P]) PopPush added in v0.2.0 

func (h *SyncDaryHeap[V, P]) PopPush(value V, priority P) (V, P)

PopPush atomically removes the root element and inserts a new element into the heap. Returns the removed root element.

func (*SyncDaryHeap[V, P]) PopValue added in v0.2.0 

func (h *SyncDaryHeap[V, P]) PopValue() (V, error)

PopValue removes and returns just the value of the root element. If the heap is empty, returns a zero value with an error.

func (*SyncDaryHeap[V, P]) Push added in v0.2.0 

func (h *SyncDaryHeap[V, P]) Push(value V, priority P)

Push inserts a new element with the given value and priority into the heap. The element is added at the end and then sifted up to maintain the heap property.

func (*SyncDaryHeap[V, P]) PushPop added in v0.2.0 

func (h *SyncDaryHeap[V, P]) PushPop(value V, priority P) (V, P)

PushPop atomically inserts a new element and removes the root element if the new element doesn't belong at the root. If the new element belongs at the root, it is returned directly. Returns either the new element or the old root element.

func (*SyncDaryHeap[V, P]) Register added in v0.2.0 

func (h *SyncDaryHeap[V, P]) Register(fn func(x, y int)) callback

Register adds a callback function to be called whenever elements in the heap swap positions. Returns a callback that can be used to deregister the function later.

func (*SyncDaryHeap[V, P]) Remove added in v0.2.0 

func (h *SyncDaryHeap[V, P]) Remove(i int) (V, P, error)

Remove deletes the element at index i from the heap and returns it. The heap property is restored by replacing the removed element with the last element and sifting it down to its appropriate position. Returns the removed element and an error if the index is out of bounds.

func (*SyncDaryHeap[V, P]) Update added in v0.2.0 

func (h *SyncDaryHeap[V, P]) Update(i int, value V, priority P) error

Update replaces the element at index i with a new value and priority. It then restores the heap property by either sifting up (if the new priority is more appropriate than its parent) or sifting down (if the new priority is less appropriate than its children). Returns an error if the index is out of bounds.

type SyncFullLeftistHeap added in v0.2.0 

type SyncFullLeftistHeap[V any, P any] struct {
	// contains filtered or unexported fields
}

SyncLeftistHeap is a thread-safe wrapper around LeftistHeap. All operations are protected by a sync.RWMutex, making it safe for concurrent use.

func NewSyncFullLeftistHeap added in v0.2.0 

func NewSyncFullLeftistHeap[V any, P any](data []HeapNode[V, P], cmp func(a, b P) bool, config HeapConfig) *SyncFullLeftistHeap[V, P]

NewSyncFullLeftistHeap constructs a new thread-safe leftist heap from the given data and comparison function. The resulting heap is safe for concurrent use.

func (*SyncFullLeftistHeap[V, P]) Clear added in v0.2.0 

func (s *SyncFullLeftistHeap[V, P]) Clear()

Clear removes all elements from the heap and resets its state. It acquires a write lock.

func (*SyncFullLeftistHeap[V, P]) Clone added in v0.2.0 

func (s *SyncFullLeftistHeap[V, P]) Clone() *SyncFullLeftistHeap[V, P]

Clone creates a deep copy of the heap structure and nodes. The returned heap is also thread-safe, but shares no data with the original. It acquires a read lock.

func (*SyncFullLeftistHeap[V, P]) Get added in v0.2.0 

func (s *SyncFullLeftistHeap[V, P]) Get(id string) (V, P, error)

Get returns the element associated with the given ID. It acquires a read lock.

func (*SyncFullLeftistHeap[V, P]) GetPriority added in v0.2.0 

func (s *SyncFullLeftistHeap[V, P]) GetPriority(id string) (P, error)

GetPriority returns the priority associated with the given ID. It acquires a read lock.

func (*SyncFullLeftistHeap[V, P]) GetValue added in v0.2.0 

func (s *SyncFullLeftistHeap[V, P]) GetValue(id string) (V, error)

GetValue returns the value associated with the given ID. It acquires a read lock.

func (*SyncFullLeftistHeap[V, P]) IsEmpty added in v0.2.0 

func (s *SyncFullLeftistHeap[V, P]) IsEmpty() bool

IsEmpty returns true if the heap contains no elements. It acquires a read lock.

func (*SyncFullLeftistHeap[V, P]) Length added in v0.2.0 

func (s *SyncFullLeftistHeap[V, P]) Length() int

Length returns the current number of elements in the heap. It acquires a read lock.

func (*SyncFullLeftistHeap[V, P]) Peek added in v0.2.0 

func (s *SyncFullLeftistHeap[V, P]) Peek() (V, P, error)

Peek returns the minimum element without removing it. It acquires a read lock.

func (*SyncFullLeftistHeap[V, P]) PeekPriority added in v0.2.0 

func (s *SyncFullLeftistHeap[V, P]) PeekPriority() (P, error)

PeekPriority returns the priority at the root without removing it. It acquires a read lock.

func (*SyncFullLeftistHeap[V, P]) PeekValue added in v0.2.0 

func (s *SyncFullLeftistHeap[V, P]) PeekValue() (V, error)

PeekValue returns the value at the root without removing it. It acquires a read lock.

func (*SyncFullLeftistHeap[V, P]) Pop added in v0.2.0 

func (s *SyncFullLeftistHeap[V, P]) Pop() (V, P, error)

Pop removes and returns the minimum element from the heap. It acquires a write lock.

func (*SyncFullLeftistHeap[V, P]) PopPriority added in v0.2.0 

func (s *SyncFullLeftistHeap[V, P]) PopPriority() (P, error)

PopPriority removes and returns just the priority at the root. It acquires a write lock.

func (*SyncFullLeftistHeap[V, P]) PopValue added in v0.2.0 

func (s *SyncFullLeftistHeap[V, P]) PopValue() (V, error)

PopValue removes and returns just the value at the root. It acquires a write lock.

func (*SyncFullLeftistHeap[V, P]) Push added in v0.2.0 

func (s *SyncFullLeftistHeap[V, P]) Push(value V, priority P) (string, error)

Push inserts a new value with the given priority into the heap. It returns the unique ID of the inserted node. This method acquires a write lock.

func (*SyncFullLeftistHeap[V, P]) UpdatePriority added in v0.2.0 

func (s *SyncFullLeftistHeap[V, P]) UpdatePriority(id string, priority P) error

UpdatePriority changes the priority of the node with the given ID and restructures the heap. It acquires a write lock.

func (*SyncFullLeftistHeap[V, P]) UpdateValue added in v0.2.0 

func (s *SyncFullLeftistHeap[V, P]) UpdateValue(id string, value V) error

UpdateValue changes the value of the node with the given ID. It acquires a write lock.

type SyncFullPairingHeap added in v0.2.0 

type SyncFullPairingHeap[V any, P any] struct {
	// contains filtered or unexported fields
}

SyncPairingHeap provides a thread-safe wrapper around PairingHeap. It uses a read-write mutex to allow concurrent reads and exclusive writes.

func NewSyncFullPairingHeap added in v0.2.0 

func NewSyncFullPairingHeap[V any, P any](data []HeapNode[V, P], cmp func(a, b P) bool, config HeapConfig) *SyncFullPairingHeap[V, P]

NewSyncPairingHeap creates a new thread-safe pairing heap from a slice of HeapPairs. The heap is initialized with the provided elements and uses the given comparison function to determine heap order. The comparison function determines the heap order (min or max). Returns an empty heap if the input slice is empty.

func (*SyncFullPairingHeap[V, P]) Clear added in v0.2.0 

func (s *SyncFullPairingHeap[V, P]) Clear()

Clear removes all elements from the heap. Resets the root to nil, size to zero, and initializes a new empty element map. The next node ID is reset to 1.

func (*SyncFullPairingHeap[V, P]) Clone added in v0.2.0 

func (s *SyncFullPairingHeap[V, P]) Clone() *SyncFullPairingHeap[V, P]

Clone creates a deep copy of the heap structure and nodes. If values or priorities are reference types, those reference values are shared between the original and cloned heaps.

func (*SyncFullPairingHeap[V, P]) Get added in v0.2.0 

func (s *SyncFullPairingHeap[V, P]) Get(id string) (V, P, error)

Get retrieves a HeapNode for the node with the given ID. Returns an error if the ID does not exist in the heap.

func (*SyncFullPairingHeap[V, P]) GetPriority added in v0.2.0 

func (s *SyncFullPairingHeap[V, P]) GetPriority(id string) (P, error)

GetPriority retrieves the priority of the node with the given ID. Returns zero value and an error if the ID does not exist in the heap.

func (*SyncFullPairingHeap[V, P]) GetValue added in v0.2.0 

func (s *SyncFullPairingHeap[V, P]) GetValue(id string) (V, error)

GetValue retrieves the value of the node with the given ID. Returns zero value and an error if the ID does not exist in the heap.

func (*SyncFullPairingHeap[V, P]) IsEmpty added in v0.2.0 

func (s *SyncFullPairingHeap[V, P]) IsEmpty() bool

IsEmpty returns true if the heap contains no elements.

func (*SyncFullPairingHeap[V, P]) Length added in v0.2.0 

func (s *SyncFullPairingHeap[V, P]) Length() int

Length returns the current number of elements in the heap.

func (*SyncFullPairingHeap[V, P]) Peek added in v0.2.0 

func (s *SyncFullPairingHeap[V, P]) Peek() (V, P, error)

Peek returns a HeapNode containing the value and priority of the root node without removing it. Returns nil and an error if the heap is empty.

func (*SyncFullPairingHeap[V, P]) PeekPriority added in v0.2.0 

func (s *SyncFullPairingHeap[V, P]) PeekPriority() (P, error)

PeekPriority returns the priority at the root without removing it. Returns zero value and an error if the heap is empty.

func (*SyncFullPairingHeap[V, P]) PeekValue added in v0.2.0 

func (s *SyncFullPairingHeap[V, P]) PeekValue() (V, error)

PeekValue returns the value at the root without removing it. Returns zero value and an error if the heap is empty.

func (*SyncFullPairingHeap[V, P]) Pop added in v0.2.0 

func (s *SyncFullPairingHeap[V, P]) Pop() (V, P, error)

Pop removes and returns a HeapNode containing the value and priority of the root node. The root's children are merged to form the new heap. Returns nil and an error if the heap is empty.

func (*SyncFullPairingHeap[V, P]) PopPriority added in v0.2.0 

func (s *SyncFullPairingHeap[V, P]) PopPriority() (P, error)

PopPriority removes and returns just the priority at the root. The root's children are merged to form the new heap. Returns zero value and an error if the heap is empty.

func (*SyncFullPairingHeap[V, P]) PopValue added in v0.2.0 

func (s *SyncFullPairingHeap[V, P]) PopValue() (V, error)

PopValue removes and returns just the value at the root. The root's children are merged to form the new heap. Returns zero value and an error if the heap is empty.

func (*SyncFullPairingHeap[V, P]) Push added in v0.2.0 

func (s *SyncFullPairingHeap[V, P]) Push(value V, priority P) (string, error)

Push adds a new element with the given value and priority to the heap. A new node is created with a unique ID and melded with the existing root. The new node becomes the root if its priority is higher than the current root's. Returns the ID of the inserted node.

func (*SyncFullPairingHeap[V, P]) UpdatePriority added in v0.2.0 

func (s *SyncFullPairingHeap[V, P]) UpdatePriority(id string, priority P) error

UpdatePriority updates the priority of a node with the given ID. Returns an error if the ID does not exist in the heap. The node is removed from its current position and reinserted into the heap to maintain the heap property. This operation may change the heap structure.

func (*SyncFullPairingHeap[V, P]) UpdateValue added in v0.2.0 

func (s *SyncFullPairingHeap[V, P]) UpdateValue(id string, value V) error

UpdateValue updates the value of a node with the given ID. Returns an error if the ID does not exist in the heap. The heap structure remains unchanged as this operation only modifies the value.

type SyncFullSkewHeap added in v0.2.0 

type SyncFullSkewHeap[V any, P any] struct {
	// contains filtered or unexported fields
}

SyncSkewHeap is a thread-safe wrapper around SkewHeap. All operations are protected by a sync.RWMutex, making it safe for concurrent use.

func NewSyncFullSkewHeap added in v0.2.0 

func NewSyncFullSkewHeap[V any, P any](data []HeapNode[V, P], cmp func(a, b P) bool, config HeapConfig) *SyncFullSkewHeap[V, P]

NewSyncFullSkewHeap constructs a new thread-safe full skew heap from the given data and comparison function. The resulting heap is safe for concurrent use.

func (*SyncFullSkewHeap[V, P]) Clear added in v0.2.0 

func (s *SyncFullSkewHeap[V, P]) Clear()

Clear removes all elements from the heap and resets its state. It acquires a write lock.

func (*SyncFullSkewHeap[V, P]) Clone added in v0.2.0 

func (s *SyncFullSkewHeap[V, P]) Clone() *SyncFullSkewHeap[V, P]

Clone creates a deep copy of the heap structure and nodes. The returned heap is also thread-safe, but shares no data with the original. It acquires a read lock.

func (*SyncFullSkewHeap[V, P]) Get added in v0.2.0 

func (s *SyncFullSkewHeap[V, P]) Get(id string) (V, P, error)

Get returns the element associated with the given ID. It acquires a read lock.

func (*SyncFullSkewHeap[V, P]) GetPriority added in v0.2.0 

func (s *SyncFullSkewHeap[V, P]) GetPriority(id string) (P, error)

GetPriority returns the priority associated with the given ID. It acquires a read lock.

func (*SyncFullSkewHeap[V, P]) GetValue added in v0.2.0 

func (s *SyncFullSkewHeap[V, P]) GetValue(id string) (V, error)

GetValue returns the value associated with the given ID. It acquires a read lock.

func (*SyncFullSkewHeap[V, P]) IsEmpty added in v0.2.0 

func (s *SyncFullSkewHeap[V, P]) IsEmpty() bool

IsEmpty returns true if the heap contains no elements. It acquires a read lock.

func (*SyncFullSkewHeap[V, P]) Length added in v0.2.0 

func (s *SyncFullSkewHeap[V, P]) Length() int

Length returns the current number of elements in the heap. It acquires a read lock.

func (*SyncFullSkewHeap[V, P]) Peek added in v0.2.0 

func (s *SyncFullSkewHeap[V, P]) Peek() (V, P, error)

Peek returns the minimum element without removing it. It acquires a read lock.

func (*SyncFullSkewHeap[V, P]) PeekPriority added in v0.2.0 

func (s *SyncFullSkewHeap[V, P]) PeekPriority() (P, error)

PeekPriority returns the priority at the root without removing it. It acquires a read lock.

func (*SyncFullSkewHeap[V, P]) PeekValue added in v0.2.0 

func (s *SyncFullSkewHeap[V, P]) PeekValue() (V, error)

PeekValue returns the value at the root without removing it. It acquires a read lock.

func (*SyncFullSkewHeap[V, P]) Pop added in v0.2.0 

func (s *SyncFullSkewHeap[V, P]) Pop() (V, P, error)

Pop removes and returns the minimum element from the heap. It acquires a write lock.

func (*SyncFullSkewHeap[V, P]) PopPriority added in v0.2.0 

func (s *SyncFullSkewHeap[V, P]) PopPriority() (P, error)

PopPriority removes and returns just the priority at the root. It acquires a write lock.

func (*SyncFullSkewHeap[V, P]) PopValue added in v0.2.0 

func (s *SyncFullSkewHeap[V, P]) PopValue() (V, error)

PopValue removes and returns just the value at the root. It acquires a write lock.

func (*SyncFullSkewHeap[V, P]) Push added in v0.2.0 

func (s *SyncFullSkewHeap[V, P]) Push(value V, priority P) (string, error)

Push inserts a new value with the given priority into the heap. It returns the unique ID of the inserted node. This method acquires a write lock.

func (*SyncFullSkewHeap[V, P]) UpdatePriority added in v0.2.0 

func (s *SyncFullSkewHeap[V, P]) UpdatePriority(id string, priority P) error

UpdatePriority changes the priority of the node with the given ID and restructures the heap. It acquires a write lock.

func (*SyncFullSkewHeap[V, P]) UpdateValue added in v0.2.0 

func (s *SyncFullSkewHeap[V, P]) UpdateValue(id string, value V) error

UpdateValue changes the value of the node with the given ID. It acquires a write lock.

type SyncLeftistHeap added in v0.2.0 

type SyncLeftistHeap[V any, P any] struct {
	// contains filtered or unexported fields
}

SyncLeftistHeap is a thread-safe wrapper around LeftistHeap. All operations are protected by a sync.RWMutex, making it safe for concurrent use.

func NewSyncLeftistHeap added in v0.2.0 

func NewSyncLeftistHeap[V any, P any](data []HeapNode[V, P], cmp func(a, b P) bool, usePool bool) *SyncLeftistHeap[V, P]

NewSyncLeftistHeap constructs a new thread-safe leftist heap from the given data and comparison function. The resulting heap is safe for concurrent use.

func (*SyncLeftistHeap[V, P]) Clear added in v0.2.0 

func (s *SyncLeftistHeap[V, P]) Clear()

Clear removes all elements from the simple heap. The heap is ready for new insertions after clearing. It acquires a write lock.

func (*SyncLeftistHeap[V, P]) Clone added in v0.2.0 

func (s *SyncLeftistHeap[V, P]) Clone() *SyncLeftistHeap[V, P]

Clone creates a deep copy of the heap structure and nodes. The returned heap is also thread-safe, but shares no data with the original. It acquires a read lock.

func (*SyncLeftistHeap[V, P]) IsEmpty added in v0.2.0 

func (s *SyncLeftistHeap[V, P]) IsEmpty() bool

IsEmpty returns true if the simple heap contains no elements. It acquires a read lock.

func (*SyncLeftistHeap[V, P]) Length added in v0.2.0 

func (s *SyncLeftistHeap[V, P]) Length() int

Length returns the current number of elements in the simple heap. It acquires a read lock.

func (*SyncLeftistHeap[V, P]) Peek added in v0.2.0 

func (s *SyncLeftistHeap[V, P]) Peek() (V, P, error)

Peek returns the minimum element without removing it. It acquires a read lock.

func (*SyncLeftistHeap[V, P]) PeekPriority added in v0.2.0 

func (s *SyncLeftistHeap[V, P]) PeekPriority() (P, error)

PeekPriority returns the priority at the root without removing it. It acquires a read lock.

func (*SyncLeftistHeap[V, P]) PeekValue added in v0.2.0 

func (s *SyncLeftistHeap[V, P]) PeekValue() (V, error)

PeekValue returns the value at the root without removing it. It acquires a read lock.

func (*SyncLeftistHeap[V, P]) Pop added in v0.2.0 

func (s *SyncLeftistHeap[V, P]) Pop() (V, P, error)

Pop removes and returns the minimum element from the simple heap. The heap property is restored through merging the root's children. It acquires a write lock.

func (*SyncLeftistHeap[V, P]) PopPriority added in v0.2.0 

func (s *SyncLeftistHeap[V, P]) PopPriority() (P, error)

PopPriority removes and returns just the priority at the root. The heap property is restored through merging the root's children. It acquires a write lock.

func (*SyncLeftistHeap[V, P]) PopValue added in v0.2.0 

func (s *SyncLeftistHeap[V, P]) PopValue() (V, error)

PopValue removes and returns just the value at the root. The heap property is restored through merging the root's children. It acquires a write lock.

func (*SyncLeftistHeap[V, P]) Push added in v0.2.0 

func (s *SyncLeftistHeap[V, P]) Push(value V, priority P)

Push adds a new element to the simple heap by creating a singleton node and merging it with the existing tree. It acquires a write lock.

type SyncPairingHeap added in v0.2.0 

type SyncPairingHeap[V any, P any] struct {
	// contains filtered or unexported fields
}

SyncPairingHeap provides a thread-safe wrapper around PairingHeap. It uses a read-write mutex to allow concurrent reads and exclusive writes.

func NewSyncPairingHeap added in v0.2.0 

func NewSyncPairingHeap[V any, P any](data []HeapNode[V, P], cmp func(a, b P) bool, usePool bool) *SyncPairingHeap[V, P]

NewSyncPairingHeap creates a new thread-safe simple pairing heap from a slice of HeapPairs. Unlike SyncPairingHeap, this implementation does not track node IDs or support node updates. It uses the provided comparison function to determine heap order (min or max). Returns an empty heap if the input slice is empty.

func (*SyncPairingHeap[V, P]) Clear added in v0.2.0 

func (s *SyncPairingHeap[V, P]) Clear()

Clear removes all elements from the simple heap. The heap is ready for new insertions after clearing.

func (*SyncPairingHeap[V, P]) Clone added in v0.2.0 

func (s *SyncPairingHeap[V, P]) Clone() *SyncPairingHeap[V, P]

Clone creates a deep copy of the simple heap structure and nodes. If values or priorities are reference types, those reference values are shared between the original and cloned heaps.

func (*SyncPairingHeap[V, P]) IsEmpty added in v0.2.0 

func (s *SyncPairingHeap[V, P]) IsEmpty() bool

IsEmpty returns true if the simple heap contains no elements.

func (*SyncPairingHeap[V, P]) Length added in v0.2.0 

func (s *SyncPairingHeap[V, P]) Length() int

Length returns the current number of elements in the simple heap.

func (*SyncPairingHeap[V, P]) Peek added in v0.2.0 

func (s *SyncPairingHeap[V, P]) Peek() (V, P, error)

Peek returns a HeapNode containing the value and priority of the root node without removing it. Returns nil and an error if the heap is empty.

func (*SyncPairingHeap[V, P]) PeekPriority added in v0.2.0 

func (s *SyncPairingHeap[V, P]) PeekPriority() (P, error)

PeekPriority returns the priority at the root without removing it. Returns zero value and an error if the heap is empty.

func (*SyncPairingHeap[V, P]) PeekValue added in v0.2.0 

func (s *SyncPairingHeap[V, P]) PeekValue() (V, error)

PeekValue returns the value at the root without removing it. Returns zero value and an error if the heap is empty.

func (*SyncPairingHeap[V, P]) Pop added in v0.2.0 

func (s *SyncPairingHeap[V, P]) Pop() (V, P, error)

Pop removes and returns a HeapNode containing the value and priority of the root node. The root's children are merged to form the new heap. Returns nil and an error if the heap is empty.

func (*SyncPairingHeap[V, P]) PopPriority added in v0.2.0 

func (s *SyncPairingHeap[V, P]) PopPriority() (P, error)

PopPriority removes and returns just the priority at the root. The root's children are merged to form the new heap. Returns zero value and an error if the heap is empty.

func (*SyncPairingHeap[V, P]) PopValue added in v0.2.0 

func (s *SyncPairingHeap[V, P]) PopValue() (V, error)

PopValue removes and returns just the value at the root. The root's children are merged to form the new heap. Returns zero value and an error if the heap is empty.

func (*SyncPairingHeap[V, P]) Push added in v0.2.0 

func (s *SyncPairingHeap[V, P]) Push(value V, priority P)

Push adds a new element with its priority by creating a single-node heap and melding it with the existing root. The new node becomes the root if its priority is higher than the current root's priority.

type SyncRadixHeap added in v0.2.0 

type SyncRadixHeap[V any, P constraints.Unsigned] struct {
	// contains filtered or unexported fields
}

SyncRadixHeap provides a thread-safe wrapper around RadixHeap. It uses a read-write mutex to allow concurrent reads and exclusive writes.

func NewSyncRadixHeap added in v0.2.0 

func NewSyncRadixHeap[V any, P constraints.Unsigned](data []HeapNode[V, P], usePool bool) *SyncRadixHeap[V, P]

NewSyncRadixHeap creates a new thread-safe RadixHeap from a given slice of HeapNode[V,P].

func (*SyncRadixHeap[V, P]) Clear added in v0.2.0 

func (s *SyncRadixHeap[V, P]) Clear()

Clear reinitializes the heap by creating fresh buckets, resetting size to zero, and setting 'last' back to its zero value.

func (*SyncRadixHeap[V, P]) Clone added in v0.2.0 

func (s *SyncRadixHeap[V, P]) Clone() *SyncRadixHeap[V, P]

Clone creates a deep copy of the heap structure. The new heap preserves the original size and last value. If values or priorities are reference types, those reference values are shared between the original and cloned heaps.

func (*SyncRadixHeap[V, P]) IsEmpty added in v0.2.0 

func (s *SyncRadixHeap[V, P]) IsEmpty() bool

IsEmpty returns true if the heap contains no items.

func (*SyncRadixHeap[V, P]) Length added in v0.2.0 

func (s *SyncRadixHeap[V, P]) Length() int

Length returns the number of items currently stored in the heap.

func (*SyncRadixHeap[V, P]) Merge added in v0.2.0 

func (s *SyncRadixHeap[V, P]) Merge(other *SyncRadixHeap[V, P])

Merge integrates another SafeRadixHeap into this one. It selects the heap with the smaller 'last' as the new baseline, adopts its buckets and 'last', then reinserts all items from the other heap to preserve the monotonic property.

func (*SyncRadixHeap[V, P]) Peek added in v0.2.0 

func (s *SyncRadixHeap[V, P]) Peek() (V, P, error)

Peek returns a HeapNode with the minimum priority without removing it. Returns nil and an error if the heap is empty.

func (*SyncRadixHeap[V, P]) PeekPriority added in v0.2.0 

func (s *SyncRadixHeap[V, P]) PeekPriority() (P, error)

PeekPriority returns just the priority of the root element without removing it. Returns zero value and an error if the heap is empty.

func (*SyncRadixHeap[V, P]) PeekValue added in v0.2.0 

func (s *SyncRadixHeap[V, P]) PeekValue() (V, error)

PeekValue returns just the value of the root element without removing it. Returns zero value and an error if the heap is empty.

func (*SyncRadixHeap[V, P]) Pop added in v0.2.0 

func (s *SyncRadixHeap[V, P]) Pop() (V, P, error)

Pop extracts and returns the HeapNode with the minimum priority. Returns nil and an error if the heap is empty.

func (*SyncRadixHeap[V, P]) PopPriority added in v0.2.0 

func (s *SyncRadixHeap[V, P]) PopPriority() (P, error)

PopPriority removes and returns just the priority of the root element. Returns zero value and an error if the heap is empty.

func (*SyncRadixHeap[V, P]) PopValue added in v0.2.0 

func (s *SyncRadixHeap[V, P]) PopValue() (V, error)

PopValue removes and returns just the value of the root element. Returns zero value and an error if the heap is empty.

func (*SyncRadixHeap[V, P]) Push added in v0.2.0 

func (s *SyncRadixHeap[V, P]) Push(value V, priority P) error

Push adds a new value and priority pair into the heap. Returns an error if the priority is less than the last extracted priority, as this would violate the monotonic property. Otherwise, puts the item into the appropriate bucket and increments the size.

func (*SyncRadixHeap[V, P]) Rebalance added in v0.2.0 

func (s *SyncRadixHeap[V, P]) Rebalance() error

Rebalance fills bucket 0 if it is empty. Returns an error if the heap is empty, or if bucket 0 already contains elements (no action was needed).

type SyncSkewHeap added in v0.2.0 

type SyncSkewHeap[V any, P any] struct {
	// contains filtered or unexported fields
}

SyncSkewHeap is a thread-safe wrapper around SkewHeap. All operations are protected by a sync.RWMutex, making it safe for concurrent use.

func NewSyncSkewHeap added in v0.2.0 

func NewSyncSkewHeap[V any, P any](data []HeapNode[V, P], cmp func(a, b P) bool, usePool bool) *SyncSkewHeap[V, P]

NewSyncSkewHeap constructs a new thread-safe skew heap from the given data and comparison function. The resulting heap is safe for concurrent use.

func (*SyncSkewHeap[V, P]) Clear added in v0.2.0 

func (s *SyncSkewHeap[V, P]) Clear()

Clear removes all elements from the simple heap. The heap is ready for new insertions after clearing. It acquires a write lock.

func (*SyncSkewHeap[V, P]) Clone added in v0.2.0 

func (s *SyncSkewHeap[V, P]) Clone() *SyncSkewHeap[V, P]

Clone creates a deep copy of the heap structure and nodes. The returned heap is also thread-safe, but shares no data with the original. It acquires a read lock.

func (*SyncSkewHeap[V, P]) IsEmpty added in v0.2.0 

func (s *SyncSkewHeap[V, P]) IsEmpty() bool

IsEmpty returns true if the simple heap contains no elements. It acquires a read lock.

func (*SyncSkewHeap[V, P]) Length added in v0.2.0 

func (s *SyncSkewHeap[V, P]) Length() int

Length returns the current number of elements in the simple heap. It acquires a read lock.

func (*SyncSkewHeap[V, P]) Peek added in v0.2.0 

func (s *SyncSkewHeap[V, P]) Peek() (V, P, error)

Peek returns the minimum element without removing it. It acquires a read lock.

func (*SyncSkewHeap[V, P]) PeekPriority added in v0.2.0 

func (s *SyncSkewHeap[V, P]) PeekPriority() (P, error)

PeekPriority returns the priority at the root without removing it. It acquires a read lock.

func (*SyncSkewHeap[V, P]) PeekValue added in v0.2.0 

func (s *SyncSkewHeap[V, P]) PeekValue() (V, error)

PeekValue returns the value at the root without removing it. It acquires a read lock.

func (*SyncSkewHeap[V, P]) Pop added in v0.2.0 

func (s *SyncSkewHeap[V, P]) Pop() (V, P, error)

Pop removes and returns the minimum element from the simple heap. The heap property is restored through merging the root's children. It acquires a write lock.

func (*SyncSkewHeap[V, P]) PopPriority added in v0.2.0 

func (s *SyncSkewHeap[V, P]) PopPriority() (P, error)

PopPriority removes and returns just the priority at the root. The heap property is restored through merging the root's children. It acquires a write lock.

func (*SyncSkewHeap[V, P]) PopValue added in v0.2.0 

func (s *SyncSkewHeap[V, P]) PopValue() (V, error)

PopValue removes and returns just the value at the root. The heap property is restored through merging the root's children. It acquires a write lock.

func (*SyncSkewHeap[V, P]) Push added in v0.2.0 

func (s *SyncSkewHeap[V, P]) Push(value V, priority P)

Push adds a new element to the simple heap by creating a singleton node and merging it with the existing tree. It acquires a write lock.

type UUIDGenerator added in v0.2.0 

type UUIDGenerator struct{}

UUIDGenerator is a generator that uses UUIDs.

func (*UUIDGenerator) Next added in v0.2.0 

func (g *UUIDGenerator) Next() string

Next returns a new UUID as a string (UUIDv4).

Source Files

View all Source files

Directories

Path Synopsis

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.