heap

package module
v1.0.0 Latest Latest
Warning

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

 Go to latest Published: Sep 23, 2025 License: Apache-2.0 Imports: 2 Imported by: 3

README

Generic Type-Safe Heap for Go

A high-performance, generic heap implementation that provides type safety, thread safety options, and compatibility with Go's standard library container/heap interface.

Features

  • Type Safety: Generic implementation using Go 1.18+ generics - no more interface{} or type assertions
  • Flexible Ordering: Support for both min-heap and max-heap through custom comparison functions
  • Thread Safety: Optional thread-safe version with optimized read operations
  • Standard Library Compatibility: Wrapper for seamless integration with container/heap

Installation

go get github.com/brunoga/heap

Quick Start

Basic Heap Usage
package main

import (
    "fmt"
    "github.com/brunoga/heap"
)

func main() {
    // Create a min-heap for integers
    minHeap := heap.NewHeap(func(a, b int) bool { return a < b })
    
    // Push some values
    minHeap.Push(3)
    minHeap.Push(1)
    minHeap.Push(4)
    minHeap.Push(2)
    
    // Pop values in sorted order
    for minHeap.Len() > 0 {
        fmt.Println(minHeap.Pop()) // Output: 1, 2, 3, 4
    }
}
Max-Heap Example
// Create a max-heap for integers
maxHeap := heap.NewHeap(func(a, b int) bool { return a > b })

maxHeap.Push(3)
maxHeap.Push(1)
maxHeap.Push(4)
maxHeap.Push(2)

fmt.Println(maxHeap.Pop()) // Output: 4 (largest first)
Custom Types
type Task struct {
    Name     string
    Priority int
}

// Priority queue (high priority first)
pq := heap.NewHeap(func(a, b Task) bool { 
    return a.Priority > b.Priority 
})

pq.Push(Task{"Low priority", 1})
pq.Push(Task{"High priority", 10})
pq.Push(Task{"Medium priority", 5})

task := pq.Pop()
fmt.Println(task.Name) // Output: "High priority"

API Reference

Core Heap (heap.Heap[T])
Constructor
  • NewHeap[T](lessFunc func(T, T) bool) *Heap[T] - Creates a new heap with custom comparison function
Methods
  • Push(item T) - Add an element (O(log n))
  • Pop() T - Remove and return the root element (O(log n))
  • Peek() T - Return the root element without removing it (O(1))
  • Len() int - Return the number of elements (O(1))
Thread-Safe Heap (heap.ThreadSafeHeap[T])

All methods from Heap[T] plus:

Constructor
  • NewThreadSafeHeap[T](lessFunc func(T, T) bool) *ThreadSafeHeap[T]
  • WrapHeapThreadSafe[T](h *Heap[T]) *ThreadSafeHeap[T]
Additional Methods
  • IsEmpty() bool - Check if heap is empty (lock-free)
  • TryPop() (T, bool) - Safe pop that won't panic on empty heap
  • TryPeek() (T, bool) - Safe peek that won't panic on empty heap
  • WithLock(fn func(*Heap[T])) - Execute function with exclusive access
  • WithRLock(fn func(*Heap[T])) - Execute function with read-only access
Standard Library Compatibility (heap.HeapWrapper[T])
Constructor
  • NewHeapWrapper[T](lessFunc func(T, T) bool) *HeapWrapper[T]
  • WrapHeap[T](h *Heap[T]) *HeapWrapper[T]
Usage with container/heap
import "container/heap"

hw := heap.NewHeapWrapper(func(a, b int) bool { return a < b })

// Use standard library functions
heap.Push(hw, 42)
min := heap.Pop(hw).(int)

// Or use embedded heap methods (faster)
hw.Heap.Push(42)
min := hw.Heap.Pop()

Performance

Benchmarks (Intel i9-9980HK @ 2.40GHz)
Operation Regular Heap Thread-Safe Heap HeapWrapper (Embedded) HeapWrapper (StdLib)
Push 14.50 ns/op 34.13 ns/op 71.05 ns/op 137.3 ns/op
Pop 136.7 ns/op 148.5 ns/op Similar to Regular Similar to Regular
Read Ops 0.5 ns/op 13.50 ns/op 0.5 ns/op 0.5 ns/op
Performance Guidelines
  1. Single-threaded applications: Use Heap[T] for best performance
  2. Multi-threaded applications: Use ThreadSafeHeap[T] (reasonable overhead)
  3. Standard library integration: Use HeapWrapper[T] with embedded methods
  4. Avoid: HeapWrapper[T] with standard library functions (significant overhead)

Thread Safety

The ThreadSafeHeap[T] implementation uses optimized RWMutex with several performance enhancements:

  • Cached Length: Len() and IsEmpty() operations are lock-free
  • Read-Write Locks: Multiple concurrent readers, exclusive writers
  • Optimized for Read-Heavy Workloads: Significant performance improvements for frequent size checks
Concurrent Usage Example
tsh := heap.NewThreadSafeHeap(func(a, b int) bool { return a < b })

// Safe to use from multiple goroutines
go func() {
    for i := 0; i < 1000; i++ {
        tsh.Push(i)
    }
}()

go func() {
    for {
        if val, ok := tsh.TryPop(); ok {
            fmt.Println("Processed:", val)
        }
    }
}()

Examples

Priority Queue for Job Scheduling
type Job struct {
    ID       int
    Priority int
    Task     string
}

jobQueue := heap.NewThreadSafeHeap(func(a, b Job) bool {
    return a.Priority > b.Priority // Higher priority first
})

// Add jobs from multiple goroutines
jobQueue.Push(Job{1, 5, "Medium priority task"})
jobQueue.Push(Job{2, 10, "High priority task"})
jobQueue.Push(Job{3, 1, "Low priority task"})

// Process jobs in priority order
for !jobQueue.IsEmpty() {
    job := jobQueue.Pop()
    fmt.Printf("Processing job %d: %s\n", job.ID, job.Task)
}
K-Smallest Elements
func kSmallest(nums []int, k int) []int {
    // Use max-heap to keep k smallest elements
    maxHeap := heap.NewHeap(func(a, b int) bool { return a > b })
    
    for _, num := range nums {
        if maxHeap.Len() < k {
            maxHeap.Push(num)
        } else if num < maxHeap.Peek() {
            maxHeap.Pop()
            maxHeap.Push(num)
        }
    }
    
    result := make([]int, 0, k)
    for maxHeap.Len() > 0 {
        result = append(result, maxHeap.Pop())
    }
    return result
}

Testing

Run the test suite:

go test -v

Run benchmarks:

go test -bench=. -benchmem

Requirements

  • Go 1.18 or later (for generics support)

Contributing

Contributions are welcome! Please feel free to submit a Pull Request.

License

This project is licensed under the APACHE 2.0 License - see the LICENSE file for details.

Acknowledgments

  • Inspired by Go's container/heap package
  • Optimized based on real-world performance testing
  • Thread-safety patterns from Go's sync package best practices

Documentation

Overview

Package heap provides a generic, type-safe heap implementation.

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type Heap 

type Heap[T any] struct {
	// contains filtered or unexported fields
}

Heap is a generic min-heap data structure. The heap property is maintained using a user-provided comparison function. For a min-heap, the function should return true if the first argument is less than the second.

The zero value is not usable; use NewHeap to create a new instance.

This implementation is not thread-safe. For concurrent use, see ThreadSafeHeap.

func NewHeap 

func NewHeap[T any](lessFunc func(i, j T) bool) *Heap[T]

NewHeap creates a new heap with the given comparison function. For a min-heap, lessFunc should return true if i < j. For a max-heap, lessFunc should return true if i > j.

Example: 

minHeap := NewHeap(func(a, b int) bool { return a < b })
maxHeap := NewHeap(func(a, b int) bool { return a > b })

func (*Heap[T]) Len 

func (h *Heap[T]) Len() int

Len returns the number of elements in the heap. Time complexity: O(1)

func (*Heap[T]) Peek 

func (h *Heap[T]) Peek() T

Peek returns the minimum element without removing it from the heap. Panics if the heap is empty. Time complexity: O(1)

func (*Heap[T]) Pop 

func (h *Heap[T]) Pop() T

Pop removes and returns the minimum element (root) from the heap. Panics if the heap is empty. Time complexity: O(log n)

func (*Heap[T]) Push 

func (h *Heap[T]) Push(item T)

Push adds an item to the heap, maintaining the heap property. Time complexity: O(log n)

type HeapWrapper 

type HeapWrapper[T any] struct {
	*Heap[T]
}

HeapWrapper wraps a type-safe Heap[T] to implement heap.Interface. This allows using the standard library's heap functions while maintaining type safety at the wrapper level.

Note: The wrapper still requires type assertions when using heap.Push/heap.Pop from the standard library, but provides a bridge for interoperability.

func NewHeapWrapper 

func NewHeapWrapper[T any](lessFunc func(i, j T) bool) *HeapWrapper[T]

NewHeapWrapper creates a new wrapper around a type-safe heap that implements heap.Interface.

func WrapHeap 

func WrapHeap[T any](h *Heap[T]) *HeapWrapper[T]

WrapHeap wraps an existing type-safe heap to implement heap.Interface.

func (*HeapWrapper[T]) Fix 

func (hw *HeapWrapper[T]) Fix(i int)

Fix re-establishes the heap ordering after the element at index i has changed its value.

func (*HeapWrapper[T]) Init 

func (hw *HeapWrapper[T]) Init()

Init initializes the heap using the standard library's heap.Init function. This is useful if you've manipulated the underlying slice directly.

func (*HeapWrapper[T]) Less 

func (hw *HeapWrapper[T]) Less(i, j int) bool

Less reports whether the element with index i should sort before index j. This satisfies sort.Interface (embedded in heap.Interface).

func (*HeapWrapper[T]) Pop 

func (hw *HeapWrapper[T]) Pop() any

Pop removes and returns the last element from the slice. This is the low-level interface method - use heap.Pop() for proper heap semantics. This satisfies heap.Interface.

func (*HeapWrapper[T]) Push 

func (hw *HeapWrapper[T]) Push(x any)

Push adds x to the heap at the end of the slice. This is the low-level interface method - use heap.Push() for proper heap semantics. This satisfies heap.Interface.

func (*HeapWrapper[T]) Remove 

func (hw *HeapWrapper[T]) Remove(i int) T

Remove removes and returns the element at index i from the heap.

func (*HeapWrapper[T]) Swap 

func (hw *HeapWrapper[T]) Swap(i, j int)

Swap swaps the elements with indexes i and j. This satisfies sort.Interface (embedded in heap.Interface).

type ThreadSafeHeap 

type ThreadSafeHeap[T any] struct {
	// contains filtered or unexported fields
}

ThreadSafeHeap wraps a Heap[T] with a RWMutex to provide thread-safe operations. It maintains the same API as Heap[T] but is safe for concurrent use by multiple goroutines. Uses optimizations for read-heavy workloads.

func NewThreadSafeHeap 

func NewThreadSafeHeap[T any](lessFunc func(i, j T) bool) *ThreadSafeHeap[T]

NewThreadSafeHeap creates a new thread-safe heap with the given comparison function.

func WrapHeapThreadSafe 

func WrapHeapThreadSafe[T any](h *Heap[T]) *ThreadSafeHeap[T]

WrapHeapThreadSafe wraps an existing heap to make it thread-safe. Note: After wrapping, the original heap should not be used directly to avoid race conditions.

func (*ThreadSafeHeap[T]) IsEmpty 

func (tsh *ThreadSafeHeap[T]) IsEmpty() bool

IsEmpty returns true if the heap is empty in a thread-safe manner. This uses the lock-free Len() method.

func (*ThreadSafeHeap[T]) Len 

func (tsh *ThreadSafeHeap[T]) Len() int

Len returns the number of elements in the heap in a thread-safe manner. This uses a cached value for lock-free reads.

func (*ThreadSafeHeap[T]) Peek 

func (tsh *ThreadSafeHeap[T]) Peek() T

Peek returns the minimum element without removing it in a thread-safe manner. Panics if the heap is empty.

func (*ThreadSafeHeap[T]) Pop 

func (tsh *ThreadSafeHeap[T]) Pop() T

Pop removes and returns the minimum element from the heap in a thread-safe manner. Panics if the heap is empty.

func (*ThreadSafeHeap[T]) Push 

func (tsh *ThreadSafeHeap[T]) Push(item T)

Push adds an item to the heap in a thread-safe manner.

func (*ThreadSafeHeap[T]) TryPeek 

func (tsh *ThreadSafeHeap[T]) TryPeek() (T, bool)

TryPeek attempts to peek at the minimum element. Returns the element and true if successful, zero value and false if empty. This is useful to avoid panics when the heap might be empty.

func (*ThreadSafeHeap[T]) TryPop 

func (tsh *ThreadSafeHeap[T]) TryPop() (T, bool)

TryPop attempts to pop an element from the heap. Returns the element and true if successful, zero value and false if empty. This is useful to avoid panics when the heap might be empty.

func (*ThreadSafeHeap[T]) WithLock 

func (tsh *ThreadSafeHeap[T]) WithLock(fn func(*Heap[T]))

WithLock provides exclusive access to the underlying heap for batch operations. The provided function is executed while holding the mutex. This is useful for performing multiple operations atomically.

Example: 

tsh.WithLock(func(h *Heap[int]) {
    h.Push(1)
    h.Push(2)
    // Both pushes happen atomically
})

func (*ThreadSafeHeap[T]) WithRLock 

func (tsh *ThreadSafeHeap[T]) WithRLock(fn func(*Heap[T]))

WithRLock provides read-only access to the underlying heap. The provided function is executed while holding the read mutex. This is useful for performing multiple read operations efficiently.

Example: 

var min, len int
tsh.WithRLock(func(h *Heap[int]) {
    min = h.Peek()
    len = h.Len()
    // Both reads happen under the same lock
})

Source Files

View all Source files

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.