fibheap

README

High-Efficiency Fibonacci Heap

Package fibheap implements a Fibonacci heap. A Fibonacci heap is a data structure for priority queue operations, consisting of a collection of heap-ordered trees.

In our implementation, we do not additionally track the key value of each element. Therefore, users should be aware that they should not insert elements with the same key into the Fibonacci heap.

We compared our package with Workiva/go-datastructures.

goos: linux
goarch: amd64
pkg: github.com/ksw2000/go-fibheap
cpu: Intel(R) Core(TM) i7-4790 CPU @ 3.60GHz
                       │  baseline.txt  │               ours.txt               │
                       │     sec/op     │    sec/op     vs base                │
HeapExtractMin100-8       122.21µ ± 12%   59.62µ ± 16%  -51.21% (p=0.000 n=10)
HeapExtractMin1000-8      6533.6µ ± 11%   804.0µ ± 11%  -87.69% (p=0.000 n=10)
HeapExtractMin10000-8    172.212m ± 10%   8.747m ± 11%  -94.92% (p=0.000 n=10)
HeapExtractMin100000-8   12685.2m ±  2%   135.1m ±  5%  -98.93% (p=0.000 n=10)
geomean                    36.34m         2.744m        -92.45%

                       │  baseline.txt   │               ours.txt               │
                       │      B/op       │     B/op      vs base                │
HeapExtractMin100-8         87.59Ki ± 0%   12.44Ki ± 0%  -85.80% (p=0.000 n=10)
HeapExtractMin1000-8       8408.9Ki ± 0%   140.5Ki ± 0%  -98.33% (p=0.000 n=10)
HeapExtractMin10000-8     817.852Mi ± 0%   1.678Mi ± 0%  -99.79% (p=0.000 n=10)
HeapExtractMin100000-8   77056.52Mi ± 0%   19.84Mi ± 0%  -99.97% (p=0.000 n=10)
geomean                     81.57Mi        497.0Ki       -99.40%

                       │ baseline.txt │              ours.txt               │
                       │  allocs/op   │  allocs/op   vs base                │
HeapExtractMin100-8        298.0 ± 0%    199.0 ± 0%  -33.22% (p=0.000 n=10)
HeapExtractMin1000-8      2.998k ± 0%   1.999k ± 0%  -33.32% (p=0.000 n=10)
HeapExtractMin10000-8     30.01k ± 0%   20.00k ± 0%  -33.36% (p=0.000 n=10)
HeapExtractMin100000-8    300.5k ± 0%   200.0k ± 0%  -33.45% (p=0.000 n=10)
geomean                   9.474k        6.316k       -33.34%

The part of code for testing benchmark.

// ours
func benchmarkHeapExtractMin(n int) {
	h := &Heap[float64, struct{}]{}
	for i := 0; i < n; i++ {
		h.Insert(float64(i), struct{}{})
	}
	for i := 0; i < n; i++ {
		h.ExtractMin()
	}
}

// github.com/Workiva/go-datastructures/fibheap
func benchmarkHeapExtractMin(n int) {
	h := heap.NewFloatFibHeap()
	for i := 0; i < n; i++ {
		h.Enqueue(float64(i))
	}
	for i := 0; i < n; i++ {
		h.DequeueMin()
	}
}

func BenchmarkHeapExtractMin100(b *testing.B) {
	for i := 0; i < b.N; i++ {
		benchmarkHeapExtractMin(100)
	}
}

Example

package main

import (
	"fmt"

	"github.com/ksw2000/go-fibheap"
)

func main() {
	h := &fibheap.Heap[int, string]{}
	nodes := make([]*fibheap.Element[int, string], 10)
	for i := range nodes {
		nodes[i] = h.Insert(i, fmt.Sprint(i))
	}
	// remove the nodes by given a key smaller
	// than all the key in the heap
	h.Remove(nodes[0], -100)
	h.Remove(nodes[2], -100)
	h.Remove(nodes[4], -100)
	h.Remove(nodes[6], -100)
	h.Remove(nodes[8], -100)

	// remove the element with minimum key
	m := h.ExtractMin()
	fmt.Printf("key: %d, val: %s\n", m.Key(), m.Value)
	// key: 1, val: 1

	// or you can fetch the minimum key without removing it
	m = h.Min()
	fmt.Printf("key: %d, val: %s\n", m.Key(), m.Value)
	// key: 3, val: 3

	// you can also decrease the key of elements in the heap
	h.Decreasing(nodes[5], 0)
	m = h.Min()
	fmt.Printf("key: %d, val: %s\n", m.Key(), m.Value)
	// key: 0, val: 5
}

Documentation

Overview

Package fibheap implements a Fibonacci heap. A Fibonacci heap is a data structure for priority queue operations, consisting of a collection of heap-ordered trees. The amortized time complexity of Fibonacci heap operations are as follows: fetching the minimum is Θ(1), extracting the minimum is O(log n), inserting is Θ(1), decreasing a key is Θ(1), and merging two heaps is Θ(1).

In our implementation, we do not additionally track the key value of each element. Therefore, users should be aware that they should not insert elements with the same key into the Fibonacci heap.

Index

• type Element
  • func (e *Element[K, V]) Key() K
• type Heap
  • func (h *Heap[K, V]) Decreasing(x *Element[K, V], key K)
  • func (h *Heap[K, V]) ExtractMin() *Element[K, V]
  • func (h *Heap[K, V]) Insert(key K, value V) *Element[K, V]
  • func (h *Heap[K, V]) Min() *Element[K, V]
  • func (h *Heap[K, V]) Remove(x *Element[K, V], minimumKey K)
  • func (h *Heap[K, V]) Size() int
  • func (h *Heap[K, V]) Union(g *Heap[K, V]) *Heap[K, V]

Examples

• Heap
• Heap.Decreasing
• Heap.Remove

Types

type Element

type Element[K constraints.Ordered, V any] struct {

	// The value stored with this element.
	Value V
	// contains filtered or unexported fields
}

func (*Element[K, V]) Key

func (e *Element[K, V]) Key() K

Key returns the key of the element e

type Heap

type Heap[K constraints.Ordered, V any] struct {
	// contains filtered or unexported fields
}

Heap represents the fibonacci heap.

Example

h := &fibheap.Heap[int, string]{}
h.Insert(3, "three")
h.Insert(2, "two")
h.Insert(1, "one")

min := h.ExtractMin()
fmt.Println(min.Key(), min.Value)

min = h.Min()
fmt.Println(min.Key(), min.Value)

Output:

1 one
2 two

func (*Heap[K, V]) Decreasing

func (h *Heap[K, V]) Decreasing(x *Element[K, V], key K)

Decreasing decreases the key of element with the minimum key with amortized running time Θ(1). If the new key k is larger or equal than the key of x, Decreasing does nothing.

Example

h := &fibheap.Heap[int, string]{}
list := []*fibheap.Element[int, string]{}
list = append(list, h.Insert(5, "one"))
list = append(list, h.Insert(6, "two"))
list = append(list, h.Insert(7, "three"))

h.Decreasing(list[0], 1)
h.Decreasing(list[1], 2)
h.Decreasing(list[2], 3)

min := h.ExtractMin()
fmt.Println(min.Key(), min.Value)

min = h.ExtractMin()
fmt.Println(min.Key(), min.Value)

min = h.ExtractMin()
fmt.Println(min.Key(), min.Value)

Output:

1 one
2 two
3 three

func (*Heap[K, V]) ExtractMin

func (h *Heap[K, V]) ExtractMin() *Element[K, V]

ExtractMin() fetches and removes the minimum key from the heap h with amortized running time O(log n)

func (*Heap[K, V]) Insert

func (h *Heap[K, V]) Insert(key K, value V) *Element[K, V]

Insert inserts the key-value pair (key, value) to the heap h and returns the inserted element with amortized running time Θ(1)

func (*Heap[K, V]) Min

func (h *Heap[K, V]) Min() *Element[K, V]

Min fetches the minimum key from the heap h with running time Θ(1)

func (*Heap[K, V]) Remove

func (h *Heap[K, V]) Remove(x *Element[K, V], minimumKey K)

Remove removes the element x by given a key minimumKey which is smaller than any key in the heap h.

Example

h := &fibheap.Heap[int, any]{}
list := []*fibheap.Element[int, any]{}
list = append(list, h.Insert(5, nil))
list = append(list, h.Insert(6, nil))
list = append(list, h.Insert(7, nil))

h.Remove(list[0], 0)
h.Remove(list[1], 0)

fmt.Println("size:", h.Size())
fmt.Println("min:", h.Min().Key())

Output:

size: 3
min: 7

func (*Heap[K, V]) Size

func (h *Heap[K, V]) Size() int

Size returns the number of elements in the heap h

func (*Heap[K, V]) Union

func (h *Heap[K, V]) Union(g *Heap[K, V]) *Heap[K, V]

Union unions the two fibonacci heaps h and g, and returns the new fibonacci heap with amortized running time Θ(1). The heap h and g will be reset after unioning.