fibHeap

README

Golang Fibonacci Heap

GoFibonacciHeap is a Golang implementation of Fibonacci Heap. This implementation is a bit different from the traditional Fibonacci Heap with an index map inside. Thanks to the index map, the internal struct 'node' no longer need to be exposed outsides the package. The index map also makes the random access to the values in the heap possible. But the union operation of this implementation is O(n) rather than O(1) of the traditional implementation.

Operations	Insert	Minimum	ExtractMin	Union	DecreaseKey	IncreaseKey	Delete	Get
Traditional Implementation	O(1)	O(1)	O(log n)¹	O(1)	O(1)¹	O(1)¹	O(log n)¹	N/A
This Implementation	O(1)	O(1)	O(log n)¹	O(n)	O(1)¹	O(1)¹	O(log n)¹	O(1)
¹ Amortized time.

##Requirements #####Download this package

go get github.com/starwander/GoFibonacciHeap

#####Implements Value interface of this package for all values going to be inserted by value interfaces

// Value is the interface that all values push into or pop from the FibHeap by value interfaces must implement.
type Value interface {
	// Tag returns the unique tag of the value.
	// The tag is used in the index map.
	Tag() interface{}
	// Key returns the key as known as the priority of the value.
	// The valid range of the key is (-inf, +inf].
	Key() float64
}

Supported Operations

• Interfaces use tag/key as inputs, treating heap as a priority queue only

• Insert: pushes the input tag/key into the heap.
• Minimum: returns the current minimum tag/key in the heap sorted by key.
• ExtractMin: returns the current minimum tag/key in the heap and then extracts them from the heap.
• DecreaseKey: decreases and updates the tag in the heap by the input key.
• IncreaseKey: increases and updates the tag in the heap by the input key.
• Delete: deletes the tag in the heap by the input.
• GetTag: searches and returns the tag/key in the heap by the input tag.
• ExtractTag: searches and extracts the tag/key in the heap by the input tag.

• Interfaces use value(Value interface) as inputs, treating heap as a priority queue and a value storage.

• InsertValue: pushes the input value into the heap.
• MinimumValue: returns the current minimum value in the heap sorted by key.
• ExtractMinValue: returns the current minimum value in the heap and then extracts the value from the heap.
• DecreaseKeyValue: decreases and updates the value in the heap by the input.
• IncreaseKeyValue: increases and updates the value in the heap by the input.
• DeleteValue: deletes the value in the heap by the input.
• GetValue: searches and returns the value in the heap by the input tag.
• ExtractValue: searches and extracts the value in the heap by the input tag.

• Common interfaces

• Union: merges the input heap in.
• Num: returns the current total number of values in the heap.
• String: provides some basic debug information of the heap.

Example

package main

import (
	"fmt"
	"github.com/starwander/GoFibonacciHeap"
)

type student struct {
	name string
	age  float64
}

func (s *student) Tag() interface{} {
	return s.name
}

func (s *student) Key() float64 {
	return s.age
}

func main() {
	heap := fibHeap.NewFibHeap()

	heap.InsertValue(&student{"John", 18.3})
	heap.InsertValue(&student{"Tom", 21.0})
	heap.InsertValue(&student{"Jessica", 19.4})
	heap.InsertValue(&student{"Amy", 23.1})

	fmt.Println(heap.Num())     // 4
	fmt.Println(heap.Minimum()) // &{John 18.3}
	fmt.Println(heap.Num())     // 4

	john := heap.GetValue("John")
	john.(*student).age = 20
	heap.IncreaseKeyValue(john)
	fmt.Println(heap.ExtractMin()) // &{Jessica 19.4}

	fmt.Println(heap.ExtractMin()) // &{John 20}
	fmt.Println(heap.Num())        // 2

	amy := heap.GetValue("Amy")
	amy.(*student).age = 16.5
	heap.DecreaseKeyValue(amy)
	fmt.Println(heap.ExtractMin()) // &{Amy 16.5}

	fmt.Println(heap.Num()) // 1
	fmt.Println(heap.ExtractValue("Tom")) // &{Tom 21}
	fmt.Println(heap.Num()) // 0
}

Reference

GoDoc

LICENSE

GoFibonacciHeap source code is licensed under the Apache Licence, Version 2.0.

Documentation

Overview

Package fibHeap implements the Fibonacci Heap priority queue. This implementation is a bit different from the traditional Fibonacci Heap by having an index map to achieve better encapsulation.

Index

• type FibHeap
  • func NewFibHeap() *FibHeap
  • func (heap *FibHeap) DecreaseKey(tag interface{}, key float64) error
  • func (heap *FibHeap) DecreaseKeyValue(value Value) error
  • func (heap *FibHeap) Delete(tag interface{}) error
  • func (heap *FibHeap) DeleteValue(value Value) error
  • func (heap *FibHeap) ExtractMin() (interface{}, float64)
  • func (heap *FibHeap) ExtractMinValue() Value
  • func (heap *FibHeap) ExtractTag(tag interface{}) (key float64)
  • func (heap *FibHeap) ExtractValue(tag interface{}) (value Value)
  • func (heap *FibHeap) GetTag(tag interface{}) (key float64)
  • func (heap *FibHeap) GetValue(tag interface{}) (value Value)
  • func (heap *FibHeap) IncreaseKey(tag interface{}, key float64) error
  • func (heap *FibHeap) IncreaseKeyValue(value Value) error
  • func (heap *FibHeap) Insert(tag interface{}, key float64) error
  • func (heap *FibHeap) InsertValue(value Value) error
  • func (heap *FibHeap) Minimum() (interface{}, float64)
  • func (heap *FibHeap) MinimumValue() Value
  • func (heap *FibHeap) Num() uint
  • func (heap *FibHeap) String() string
  • func (heap *FibHeap) Union(anotherHeap *FibHeap) error
• type Value

Types

type FibHeap

type FibHeap struct {
	// contains filtered or unexported fields
}

FibHeap represents a Fibonacci Heap. Please note that all methods of FibHeap are not concurrent safe.

func NewFibHeap

func NewFibHeap() *FibHeap

NewFibHeap creates an initialized Fibonacci Heap.

func (*FibHeap) DecreaseKey

func (heap *FibHeap) DecreaseKey(tag interface{}, key float64) error

DecreaseKey updates the tag in the heap by the input key. If the input key has a larger key or -inf key, an error will be returned. If the input tag is not existed in the heap, an error will be returned. DecreaseKey will check the nil interface but not the interface with nil value. Try to input of an interface with nil value will cause invalid address panic.

func (*FibHeap) DecreaseKeyValue

func (heap *FibHeap) DecreaseKeyValue(value Value) error

DecreaseKeyValue updates the value in the heap by the input value. If the input value has a larger key or -inf key, an error will be returned. If the tag of the input value is not existed in the heap, an error will be returned. DecreaseKeyValue will check the nil interface but not the interface with nil value. Try to input of an interface with nil value will cause invalid address panic.

func (*FibHeap) Delete

func (heap *FibHeap) Delete(tag interface{}) error

Delete deletes the input tag in the heap. If the input tag is not existed in the heap, an error will be returned. Delete will check the nil interface but not the interface with nil value. Try to input of an interface with nil value will cause invalid address panic.

func (*FibHeap) DeleteValue

func (heap *FibHeap) DeleteValue(value Value) error

DeleteValue deletes the value in the heap by the input value. If the tag of the input value is not existed in the heap, an error will be returned. DeleteValue will check the nil interface but not the interface with nil value. Try to input of an interface with nil value will cause invalid address panic.

func (*FibHeap) ExtractMin

func (heap *FibHeap) ExtractMin() (interface{}, float64)

ExtractMin returns the current minimum tag and key in the heap and then extracts them from the heap. An empty heap will return nil/-inf and extracts nothing.

func (*FibHeap) ExtractMinValue

func (heap *FibHeap) ExtractMinValue() Value

ExtractMinValue returns the current minimum value in the heap and then extracts it from the heap. An empty heap will return nil and extracts nothing.

func (*FibHeap) ExtractTag

func (heap *FibHeap) ExtractTag(tag interface{}) (key float64)

ExtractTag searches and extracts the tag/key in the heap by the input tag. If the input tag does not exist in the heap, nil will be returned. ExtractTag will extract the value so the value will no longer exist in the heap.

func (*FibHeap) ExtractValue

func (heap *FibHeap) ExtractValue(tag interface{}) (value Value)

ExtractValue searches and extracts the value in the heap by the input tag. If the input tag does not exist in the heap, nil will be returned. ExtractValue will extract the value so the value will no longer exist in the heap.

func (*FibHeap) GetTag

func (heap *FibHeap) GetTag(tag interface{}) (key float64)

GetTag searches and returns the key in the heap by the input tag. If the input tag does not exist in the heap, nil will be returned. GetTag will not extract the value so the value will still exist in the heap.

func (*FibHeap) GetValue

func (heap *FibHeap) GetValue(tag interface{}) (value Value)

GetValue searches and returns the value in the heap by the input tag. If the input tag does not exist in the heap, nil will be returned. GetValue will not extract the value so the value will still exist in the heap.

func (*FibHeap) IncreaseKey

func (heap *FibHeap) IncreaseKey(tag interface{}, key float64) error

IncreaseKey updates the tag in the heap by the input key. If the input key has a smaller key or -inf key, an error will be returned. If the input tag is not existed in the heap, an error will be returned. IncreaseKey will check the nil interface but not the interface with nil value. Try to input of an interface with nil value will cause invalid address panic.

func (*FibHeap) IncreaseKeyValue

func (heap *FibHeap) IncreaseKeyValue(value Value) error

IncreaseKeyValue updates the value in the heap by the input value. If the input value has a smaller key or -inf key, an error will be returned. If the tag of the input value is not existed in the heap, an error will be returned. IncreaseKeyValue will check the nil interface but not the interface with nil value. Try to input of an interface with nil value will cause invalid address panic.

func (*FibHeap) Insert

func (heap *FibHeap) Insert(tag interface{}, key float64) error

Insert pushes the input tag and key into the heap. Try to insert a duplicate tag value will cause an error return. The valid range of the key is (-inf, +inf]. Try to insert a -inf key value will cause an error return. Insert will check the nil interface but not the interface with nil value. Try to input of an interface with nil value will cause invalid address panic.

func (*FibHeap) InsertValue

func (heap *FibHeap) InsertValue(value Value) error

InsertValue pushes the input value into the heap. The input value must implements the Value interface. Try to insert a duplicate tag value will cause an error return. The valid range of the value's key is (-inf, +inf]. Try to insert a -inf key value will cause an error return. Insert will check the nil interface but not the interface with nil value. Try to input of an interface with nil value will cause invalid address panic.

func (*FibHeap) Minimum

func (heap *FibHeap) Minimum() (interface{}, float64)

Minimum returns the current minimum tag and key in the heap sorted by the key. Minimum will not extract the tag and key so the value will still exists in the heap. An empty heap will return nil and -inf.

func (*FibHeap) MinimumValue

func (heap *FibHeap) MinimumValue() Value

MinimumValue returns the current minimum value in the heap sorted by the key. MinimumValue will not extract the value so the value will still exists in the heap. An empty heap will return nil.

func (*FibHeap) Num

func (heap *FibHeap) Num() uint

Num returns the total number of values in the heap.

func (*FibHeap) String

func (heap *FibHeap) String() string

String provides some basic debug information of the heap. It returns the total number, roots size, index size and current minimum value of the heap. It also returns the topology of the trees by dfs search.

func (*FibHeap) Union

func (heap *FibHeap) Union(anotherHeap *FibHeap) error

Union merges the input heap in. All values of the input heap must not have duplicate tags. Otherwise an error will be returned.

type Value

type Value interface {
	// Tag returns the unique tag of the value.
	// The tag is used in the index map.
	Tag() interface{}
	// Key returns the key as known as the priority of the value.
	// The valid range of the key is (-inf, +inf].
	Key() float64
}

Value is the interface that all values push into or pop from the FibHeap by value interfaces must implement.