README
¶
Heap Package
This package provides thread-safe implementations of various heap data structures in Go, including binary heaps, advanced heaps, and a priority queue.
Features
Basic Heaps
- MinHeap: Root is the minimum element
- MaxHeap: Root is the maximum element
- Common operations:
- Insert: Add new element
- Extract: Remove root element
- Peek: View root element
- Size/IsEmpty checks
Advanced Heaps
- Fibonacci Heap:
- Amortized O(1) for insert and decrease-key
- Efficient merge operations
- Marked nodes for cascading cuts
- Binomial Heap:
- Tree-based implementation
- Efficient merge operations
- Logarithmic height guarantee
- Leftist Heap:
- Self-adjusting structure
- Efficient merge operations
- Path length optimization
- Skew Heap:
- Self-adjusting structure
- Simpler than leftist heap
- Probabilistic balance
Priority Queue
- Generic value storage with interface{} type
- Priority-based ordering
- FIFO behavior for equal priorities
- Thread-safe operations
- Core operations:
- Enqueue: Add with priority
- Dequeue: Remove highest priority
- Peek: View highest priority
Usage Examples
Basic Heap Operations
// MinHeap
minHeap := NewMinHeap()
minHeap.Insert(5)
minHeap.Insert(3)
min, _ := minHeap.Extract() // returns 3
// MaxHeap
maxHeap := NewMaxHeap()
maxHeap.Insert(5)
maxHeap.Insert(3)
max, _ := maxHeap.Extract() // returns 5
Fibonacci Heap
fibHeap := NewFibonacciHeap()
fibHeap.Insert(10)
fibHeap.Insert(5)
fibHeap.Insert(15)
min, _ := fibHeap.Extract() // returns 5
value, _ := fibHeap.Peek() // returns 10
Priority Queue
pq := NewPriorityQueue()
// Add items with priorities
pq.Enqueue("high", 3)
pq.Enqueue("medium", 2)
pq.Enqueue("low", 1)
// Get highest priority item
value, _ := pq.Dequeue() // returns "high"
Implementation Details
Time Complexities
Basic Heaps (Min/Max)
- Insert: O(log n)
- Extract: O(log n)
- Peek: O(1)
- Size/IsEmpty: O(1)
Fibonacci Heap
- Insert: O(1)
- Extract-Min: O(log n) amortized
- Decrease-Key: O(1) amortized
- Merge: O(1)
Priority Queue
- Enqueue: O(log n)
- Dequeue: O(log n)
- Peek: O(1)
Space Complexities
- Binary Heaps: O(n)
- Fibonacci Heap: O(n)
- Priority Queue: O(n)
Thread Safety
- All operations are protected with RWMutex
- Read operations use RLock
- Write operations use Lock
- Proper lock/unlock handling with defer
Special Features
-
Fibonacci Heap:
- Lazy merging of trees
- Marked nodes for optimizing decrease-key
- Degree-based consolidation
-
Priority Queue:
- FIFO ordering for equal priorities
- Generic value storage
- Index tracking for stable sorting
Testing
Each heap implementation comes with comprehensive test coverage. Run tests using:
go test ./...
Contributing
Contributions are welcome! Please ensure that any new features or modifications come with:
- Proper documentation
- Thread safety considerations
- Comprehensive test cases
- Example usage
- Time complexity analysis
License
This package is distributed under the MIT license. See the LICENSE file for more details.
Documentation
¶
Overview ¶
Package heap implements various heap data structures
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type BinomialHeap ¶
type BinomialHeap struct {
// contains filtered or unexported fields
}
BinomialHeap represents a binomial heap data structure
func NewBinomialHeap ¶
func NewBinomialHeap() *BinomialHeap
NewBinomialHeap creates and returns a new instance of BinomialHeap
func (*BinomialHeap) Extract ¶
func (bh *BinomialHeap) Extract() (int, error)
Extract removes and returns the minimum element from the heap
func (*BinomialHeap) Insert ¶
func (bh *BinomialHeap) Insert(value int)
Insert adds a new value to the binomial heap
func (*BinomialHeap) IsEmpty ¶
func (bh *BinomialHeap) IsEmpty() bool
IsEmpty returns true if the heap contains no elements
func (*BinomialHeap) Peek ¶
func (bh *BinomialHeap) Peek() (int, error)
Peek returns the minimum element without removing it
func (*BinomialHeap) Size ¶
func (bh *BinomialHeap) Size() int
Size returns the number of elements in the heap
type BinomialNode ¶
type BinomialNode struct {
// contains filtered or unexported fields
}
BinomialNode represents a node in the binomial heap
type FibNode ¶
type FibNode struct {
// contains filtered or unexported fields
}
FibNode represents a node in the Fibonacci heap
type FibonacciHeap ¶
type FibonacciHeap struct {
// contains filtered or unexported fields
}
FibonacciHeap represents a Fibonacci heap data structure
func NewFibonacciHeap ¶
func NewFibonacciHeap() *FibonacciHeap
NewFibonacciHeap creates and returns a new instance of FibonacciHeap
func (*FibonacciHeap) DecreaseKey ¶
func (fh *FibonacciHeap) DecreaseKey(node *FibNode, newKey int) error
DecreaseKey decreases the key of a node
func (*FibonacciHeap) Extract ¶
func (fh *FibonacciHeap) Extract() (int, error)
Extract removes and returns the minimum element from the heap
func (*FibonacciHeap) Insert ¶
func (fh *FibonacciHeap) Insert(value int)
Insert adds a new value to the Fibonacci heap
func (*FibonacciHeap) IsEmpty ¶
func (fh *FibonacciHeap) IsEmpty() bool
IsEmpty returns true if the heap contains no elements
func (*FibonacciHeap) Peek ¶
func (fh *FibonacciHeap) Peek() (int, error)
Peek returns the minimum element without removing it
func (*FibonacciHeap) Size ¶
func (fh *FibonacciHeap) Size() int
Size returns the number of elements in the heap
type IHeap ¶
type IHeap interface {
// Insert adds a new element to the heap
Insert(value int)
// Extract removes and returns the root element (min for MinHeap, max for MaxHeap)
Extract() (int, error)
// Peek returns the root element without removing it
Peek() (int, error)
// Size returns the number of elements in the heap
Size() int
// IsEmpty returns true if the heap has no elements
IsEmpty() bool
}
IHeap interface defines the basic operations that all heap implementations must provide
type LeftistHeap ¶ added in v1.1.0
type LeftistHeap struct {
// contains filtered or unexported fields
}
LeftistHeap represents a leftist heap data structure
func NewLeftistHeap ¶ added in v1.1.0
func NewLeftistHeap() *LeftistHeap
NewLeftistHeap creates a new empty leftist heap
func (*LeftistHeap) Clear ¶ added in v1.1.0
func (lh *LeftistHeap) Clear()
Clear removes all elements from the heap
func (*LeftistHeap) DeleteMin ¶ added in v1.1.0
func (lh *LeftistHeap) DeleteMin() (int, bool)
DeleteMin removes and returns the minimum element
func (*LeftistHeap) FindMin ¶ added in v1.1.0
func (lh *LeftistHeap) FindMin() (int, bool)
FindMin returns the minimum element without removing it
func (*LeftistHeap) Insert ¶ added in v1.1.0
func (lh *LeftistHeap) Insert(key int)
Insert adds a new key to the heap
func (*LeftistHeap) IsEmpty ¶ added in v1.1.0
func (lh *LeftistHeap) IsEmpty() bool
IsEmpty returns true if the heap is empty
func (*LeftistHeap) Merge ¶ added in v1.1.0
func (lh *LeftistHeap) Merge(other *LeftistHeap)
Merge combines two leftist heaps into one
func (*LeftistHeap) Size ¶ added in v1.1.0
func (lh *LeftistHeap) Size() int
Size returns the number of elements in the heap
type LeftistNode ¶ added in v1.1.0
type LeftistNode struct {
// contains filtered or unexported fields
}
LeftistNode represents a node in the Leftist Heap
type MaxHeapImpl ¶
type MaxHeapImpl struct {
// contains filtered or unexported fields
}
MaxHeapImpl represents a binary heap data structure that maintains the max-heap property
func NewMaxHeap ¶
func NewMaxHeap() *MaxHeapImpl
NewMaxHeap creates and returns a new instance of MaxHeapImpl
func (*MaxHeapImpl) Extract ¶
func (h *MaxHeapImpl) Extract() (int, error)
Extract removes and returns the maximum element from the heap
func (*MaxHeapImpl) Insert ¶
func (h *MaxHeapImpl) Insert(value int)
Insert adds a new value to the heap while maintaining the max-heap property
func (*MaxHeapImpl) IsEmpty ¶
func (h *MaxHeapImpl) IsEmpty() bool
IsEmpty returns true if the heap contains no elements
func (*MaxHeapImpl) Peek ¶
func (h *MaxHeapImpl) Peek() (int, error)
Peek returns the maximum element without removing it
func (*MaxHeapImpl) Size ¶
func (h *MaxHeapImpl) Size() int
Size returns the number of elements in the heap
type MinHeapImpl ¶
type MinHeapImpl struct {
// contains filtered or unexported fields
}
MinHeapImpl represents a binary heap data structure that maintains the min-heap property
func NewMinHeap ¶
func NewMinHeap() *MinHeapImpl
NewMinHeap creates and returns a new instance of MinHeapImpl
func (*MinHeapImpl) Extract ¶
func (h *MinHeapImpl) Extract() (int, error)
Extract removes and returns the minimum element from the heap
func (*MinHeapImpl) Insert ¶
func (h *MinHeapImpl) Insert(value int)
Insert adds a new value to the heap while maintaining the min-heap property
func (*MinHeapImpl) IsEmpty ¶
func (h *MinHeapImpl) IsEmpty() bool
IsEmpty returns true if the heap contains no elements
func (*MinHeapImpl) Peek ¶
func (h *MinHeapImpl) Peek() (int, error)
Peek returns the minimum element without removing it
func (*MinHeapImpl) Size ¶
func (h *MinHeapImpl) Size() int
Size returns the number of elements in the heap
type PriorityQueue ¶
type PriorityQueue struct {
// contains filtered or unexported fields
}
PriorityQueue implements a priority queue using a min heap
func NewPriorityQueue ¶
func NewPriorityQueue() *PriorityQueue
NewPriorityQueue creates and returns a new instance of PriorityQueue
func (*PriorityQueue) Dequeue ¶
func (pq *PriorityQueue) Dequeue() (interface{}, error)
Dequeue removes and returns the highest priority item
func (*PriorityQueue) Enqueue ¶
func (pq *PriorityQueue) Enqueue(value interface{}, priority int)
Enqueue adds a new item to the priority queue
func (*PriorityQueue) IsEmpty ¶
func (pq *PriorityQueue) IsEmpty() bool
IsEmpty returns true if the priority queue contains no elements
func (*PriorityQueue) Peek ¶
func (pq *PriorityQueue) Peek() (interface{}, error)
Peek returns the highest priority item without removing it
func (*PriorityQueue) Size ¶
func (pq *PriorityQueue) Size() int
Size returns the number of elements in the priority queue
type SkewHeap ¶ added in v1.1.0
type SkewHeap struct {
// contains filtered or unexported fields
}
SkewHeap represents a skew heap data structure
func NewSkewHeap ¶ added in v1.1.0
func NewSkewHeap() *SkewHeap
NewSkewHeap creates a new empty skew heap
func (*SkewHeap) Clear ¶ added in v1.1.0
func (sh *SkewHeap) Clear()
Clear removes all elements from the heap
Source Files