go_heaps

README

go-heaps

Reference implementations of heap data structures in Go

Installation

$ go get -u github.com/theodesp/go-heaps

Contents

Heaps

• Pairing Heap: A pairing heap is a type of heap data structure with relatively simple implementation and excellent practical amortized performance,

Usage

package main

import (
	pairingHeap "go-heaps/pairing"
	"fmt"
)

func main()  {
	heap := pairingHeap.NewWithIntComparator()
	heap.Insert(4)
	heap.Insert(3)
	heap.Insert(2)
	heap.Insert(5)

	fmt.Println(heap.DeleteMin()) // 2
	fmt.Println(heap.DeleteMin()) // 3
	fmt.Println(heap.DeleteMin()) // 4
	fmt.Println(heap.DeleteMin()) // 5
}

Complexity

Operation	Pairing
FindMin	Θ(1)
DeleteMin	O(log n)
Insert	Θ(1)
Find	O(n)
Delete	O(log n)
Adjust	O(log n)

LICENCE

Copyright © 2017 Theo Despoudis MIT license

Documentation

Index

• Constants
• func IntComparator(a, b interface{}) int
• func StringComparator(a, b interface{}) int
• type Comparator
• type Interface

Constants

const Version = "0.0.1"

Version The main version number that is being run at the moment.

Functions

func IntComparator

func IntComparator(a, b interface{}) int

IntComparator provides a basic comparison on int

func StringComparator

func StringComparator(a, b interface{}) int

StringComparator provides a fast comparison on strings

Types

type Comparator

type Comparator func(a, b interface{}) int

Comparator will make type assertion (see IntComparator for example), which will panic if a or b are not of the asserted type.

Should return a number:

negative , if a < b
zero     , if a == b
positive , if a > b

type Interface

type Interface interface {
	// Inserts an element to the heap and returns it
	Insert(v interface{}) interface{}

	// DeleteMin deletes and returns the smallest element
	DeleteMin() interface{}

	// FindMin returns the minimum element
	FindMin() interface{}

	// Removes all items
	Clear()
}

Interface is basic interface that all Heaps implement.