heap

README

D-Ary Heap Implementation in Go

Introduction

This package provides a generic implementation of a d-ary heap in Go, suitable for any ordered type. A d-ary heap is a generalization of a binary heap where each node has d children instead of two. This variation allows for a more shallow heap, potentially optimizing operations like decrease-key, which benefits from a shorter path from any given node to the root.

Why Use a D-Ary Heap?

The d-ary heap is particularly useful in scenarios where heap operations are a bottleneck in performance. Due to its more shallow structure compared to a binary heap, operations that move elements between the root and the leaf nodes (like insertions and deletions) can be faster, as they generally involve fewer steps. This makes d-ary heaps an excellent choice for priority queues, especially when managing large datasets or when fine-tuning performance is necessary.

Installation

To use this package, simply import it into your Go project:

import "github.com/ahrav/go-d-ary-heap"

Usage

Below are examples demonstrating how to use this d-ary heap implementation with different types and operations.

Creating a New Heap

package main

import (
    "fmt"
    "github.com/ahrav/go-d-ary-heap"
)

func main() {
    // Create a min-heap for integers with a branching factor of 3.
    minHeap := heap.NewHeap[int](3, func(a, b int) bool { return a < b })

    // Create a max-heap for integers with a branching factor of 4.
    maxHeap := heap.NewHeap[int](4, func(a, b int) bool { return a > b })
}

Adding Elements

minHeap.Push(10)
minHeap.Push(5)
minHeap.Push(15)

maxHeap.Push(10)
maxHeap.Push(5)
maxHeap.Push(15)

Removing the Extremal Element

fmt.Println(minHeap.Pop()) // Outputs: 5
fmt.Println(maxHeap.Pop()) // Outputs: 15

Peeking at the Extremal Element

fmt.Println(minHeap.Peek()) // Assuming more elements were added, outputs the smallest
fmt.Println(maxHeap.Peek()) // Assuming more elements were added, outputs the largest

Contributing

Contributions to improve the d-ary heap implementation are welcome. Please feel free to submit pull requests or open issues to discuss potential improvements or report bugs.

Documentation

Index

• type Heap
  • func NewHeap[T constraints.Ordered](d int, less func(T, T) bool, options ...Option[T]) *Heap[T]
  • func (h *Heap[T]) Peek() T
  • func (h *Heap[T]) Pop() T
  • func (h *Heap[T]) Push(value T)
• type Option
  • func WithCapacity[T constraints.Ordered](capacity int) Option[T]

Types

type Heap

type Heap[T constraints.Ordered] struct {
	// contains filtered or unexported fields
}

Heap struct represents a generic d-ary heap.

func NewHeap

func NewHeap[T constraints.Ordered](d int, less func(T, T) bool, options ...Option[T]) *Heap[T]

NewHeap creates a new d-ary heap with the specified branching factor.

func (*Heap[T]) Peek

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

Peek returns the minimum element from the heap without removing it.

func (*Heap[T]) Pop

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

Pop removes and returns the minimum element from the heap.

func (*Heap[T]) Push

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

Push adds a new element to the heap.

type Option

type Option[T constraints.Ordered] func(*Heap[T])

Option is a type representing configurations for the heap

func WithCapacity

func WithCapacity[T constraints.Ordered](capacity int) Option[T]

WithCapacity is an option that sets the initial capacity of the heap