## Documentation

### Overview ¶

Package fibheap is an implementation of a priority queue backed by a Fibonacci heap, as described by Fredman and Tarjan. Fibonacci heaps are interesting theoretically because they have asymptotically good runtime guarantees for many operations. In particular, insert, peek, and decrease-key all run in amortized O(1) time. dequeueMin and delete each run in amortized O(lg n) time. This allows algorithms that rely heavily on decrease-key to gain significant performance boosts. For example, Dijkstra's algorithm for single-source shortest paths can be shown to run in O(m + n lg n) using a Fibonacci heap, compared to O(m lg n) using a standard binary or binomial heap.

Internally, a Fibonacci heap is represented as a circular, doubly-linked list of trees obeying the min-heap property. Each node stores pointers to its parent (if any) and some arbitrary child. Additionally, every node stores its degree (the number of children it has) and whether it is a "marked" node. Finally, each Fibonacci heap stores a pointer to the tree with the minimum value.

To insert a node into a Fibonacci heap, a singleton tree is created and merged into the rest of the trees. The merge operation works by simply splicing together the doubly-linked lists of the two trees, then updating the min pointer to be the smaller of the minima of the two heaps. Peeking at the smallest element can therefore be accomplished by just looking at the min element. All of these operations complete in O(1) time.

The tricky operations are dequeueMin and decreaseKey. dequeueMin works by removing the root of the tree containing the smallest element, then merging its children with the topmost roots. Then, the roots are scanned and merged so that there is only one tree of each degree in the root list. This works by maintaining a dynamic array of trees, each initially null, pointing to the roots of trees of each dimension. The list is then scanned and this array is populated. Whenever a conflict is discovered, the appropriate trees are merged together until no more conflicts exist. The resulting trees are then put into the root list. A clever analysis using the potential method can be used to show that the amortized cost of this operation is O(lg n), see "Introduction to Algorithms, Second Edition" by Cormen, Rivest, Leiserson, and Stein for more details.

The other hard operation is decreaseKey, which works as follows. First, we update the key of the node to be the new value. If this leaves the node smaller than its parent, we're done. Otherwise, we cut the node from its parent, add it as a root, and then mark its parent. If the parent was already marked, we cut that node as well, recursively mark its parent, and continue this process. This can be shown to run in O(1) amortized time using yet another clever potential function. Finally, given this function, we can implement delete by decreasing a key to -\infty, then calling dequeueMin to extract it.

## Example ¶

Code:

```
package main
// Example usage of the Fibonacci heap
import (
"fmt"
)
const SomeNumberAround0 float64 = -0.001
const SomeLargerNumberAround15 float64 = 15.77
const SomeNumberAroundMinus1000 float64 = -1002.2001
const SomeNumberAroundMinus1003 float64 = -1003.4
func main() {
heap1 := NewFloatFibHeap()
fmt.Println("Created heap 1.")
nodeh1_1 := heap1.Enqueue(SomeLargerNumberAround15)
fmt.Printf("Heap 1 insert: %v\n", nodeh1_1.Priority)
heap2 := NewFloatFibHeap()
fmt.Println("Created heap 2.")
fmt.Printf("Heap 2 is empty? %v\n", heap2.IsEmpty())
nodeh2_1 := heap2.Enqueue(SomeNumberAroundMinus1000)
fmt.Printf("Heap 2 insert: %v\n", nodeh2_1.Priority)
nodeh2_2 := heap2.Enqueue(SomeNumberAround0)
fmt.Printf("Heap 2 insert: %v\n", nodeh2_2.Priority)
fmt.Printf("Heap 1 size: %v\n", heap1.Size())
fmt.Printf("Heap 2 size: %v\n", heap2.Size())
fmt.Printf("Heap 1 is empty? %v\n", heap1.IsEmpty())
fmt.Printf("Heap 2 is empty? %v\n", heap2.IsEmpty())
fmt.Printf("\nMerge Heap 1 and Heap 2.\n")
mergedHeap, _ := heap1.Merge(&heap2)
fmt.Printf("Merged heap size: %v\n", mergedHeap.Size())
fmt.Printf("Set node with priority %v to new priority %v\n", SomeNumberAroundMinus1000, SomeNumberAroundMinus1003)
mergedHeap.DecreaseKey(nodeh2_1, SomeNumberAroundMinus1003)
min, _ := mergedHeap.DequeueMin()
fmt.Printf("Dequeue minimum of merged heap: %v\n", min.Priority)
fmt.Printf("Merged heap size: %v\n", mergedHeap.Size())
fmt.Printf("Delete from merged heap: %v\n", SomeNumberAround0)
mergedHeap.Delete(nodeh2_2)
fmt.Printf("Merged heap size: %v\n", mergedHeap.Size())
min, _ = mergedHeap.DequeueMin()
fmt.Printf("Extracting minimum of merged heap: %v\n", min.Priority)
fmt.Printf("Merged heap size: %v\n", mergedHeap.Size())
fmt.Printf("Merged heap is empty? %v\n", mergedHeap.IsEmpty())
}
```

Created heap 1. Heap 1 insert: 15.77 Created heap 2. Heap 2 is empty? true Heap 2 insert: -1002.2001 Heap 2 insert: -0.001 Heap 1 size: 1 Heap 2 size: 2 Heap 1 is empty? false Heap 2 is empty? false Merge Heap 1 and Heap 2. Merged heap size: 3 Set node with priority -1002.2001 to new priority -1003.4 Dequeue minimum of merged heap: -1003.4 Merged heap size: 2 Delete from merged heap: -0.001 Merged heap size: 1 Extracting minimum of merged heap: 15.77 Merged heap size: 0 Merged heap is empty? true

### Index ¶

- type EmptyHeapError
- type Entry
- type FloatingFibonacciHeap
- func (heap *FloatingFibonacciHeap) DecreaseKey(node *Entry, newPriority float64) (*Entry, error)
- func (heap *FloatingFibonacciHeap) Delete(node *Entry) error
- func (heap *FloatingFibonacciHeap) DequeueMin() (*Entry, error)
- func (heap *FloatingFibonacciHeap) Enqueue(priority float64) *Entry
- func (heap *FloatingFibonacciHeap) IsEmpty() bool
- func (heap *FloatingFibonacciHeap) Merge(other *FloatingFibonacciHeap) (FloatingFibonacciHeap, error)
- func (heap *FloatingFibonacciHeap) Min() (*Entry, error)
- func (heap *FloatingFibonacciHeap) Size() uint

- type NilError

#### Examples ¶

### Constants ¶

### Variables ¶

### Functions ¶

### Types ¶

#### type EmptyHeapError ¶

type EmptyHeapError string

EmptyHeapError fires when the heap is empty and an operation could not be completed for that reason. Its string holds additional data.

#### func (EmptyHeapError) Error ¶

func (e EmptyHeapError) Error() string

#### type Entry ¶

type Entry struct { // Priority is the numerical priority of the node Priority float64 // contains filtered or unexported fields }

Entry is the entry type that will be used for each node of the Fibonacci heap

#### type FloatingFibonacciHeap ¶

```
type FloatingFibonacciHeap struct {
// contains filtered or unexported fields
}
```

FloatingFibonacciHeap is an implementation of a fibonacci heap with only floating-point priorities and no user data attached.

#### func NewFloatFibHeap ¶

func NewFloatFibHeap() FloatingFibonacciHeap

NewFloatFibHeap creates a new, empty, Fibonacci heap object.

#### func (*FloatingFibonacciHeap) DecreaseKey ¶

func (heap *FloatingFibonacciHeap) DecreaseKey(node *Entry, newPriority float64) (*Entry, error)

DecreaseKey decreases the key of the given element, sets it to the new given priority and returns the node if successfully set

## Example ¶

Code:

heap := NewFloatFibHeap() node := heap.Enqueue(SomeNumber) min, _ := heap.Min() fmt.Printf("Minimal element before decreasing key: %v\n", min.Priority) heap.DecreaseKey(node, SomeSmallerNumber) min, _ = heap.Min() fmt.Printf("Minimal element after decreasing key: %v\n", min.Priority)

Minimal element before decreasing key: 15.5 Minimal element after decreasing key: -10.1

#### func (*FloatingFibonacciHeap) Delete ¶

func (heap *FloatingFibonacciHeap) Delete(node *Entry) error

Delete deletes the given element in the heap

## Example ¶

Code:

heap := NewFloatFibHeap() node := heap.Enqueue(SomeNumber) heap.Enqueue(SomeLargerNumber) min, _ := heap.Min() fmt.Printf("Minimal element before deletion: %v\n", min.Priority) heap.Delete(node) min, _ = heap.Min() fmt.Printf("Minimal element after deletion: %v\n", min.Priority)

Minimal element before deletion: 15.5 Minimal element after deletion: 112.211

#### func (*FloatingFibonacciHeap) DequeueMin ¶

func (heap *FloatingFibonacciHeap) DequeueMin() (*Entry, error)

DequeueMin removes and returns the minimal element in the heap

## Example ¶

Code:

heap := NewFloatFibHeap() heap.Enqueue(SomeNumber) node, _ := heap.DequeueMin() fmt.Printf("Dequeueing minimal element: %v\n", node.Priority)

Dequeueing minimal element: 15.5

#### func (*FloatingFibonacciHeap) Enqueue ¶

func (heap *FloatingFibonacciHeap) Enqueue(priority float64) *Entry

Enqueue adds and element to the heap

## Example ¶

Code:

heap := NewFloatFibHeap() // The function returns a pointer // to the node that contains the new value node := heap.Enqueue(SomeNumber) fmt.Println(node.Priority)

15.5

#### func (*FloatingFibonacciHeap) IsEmpty ¶

func (heap *FloatingFibonacciHeap) IsEmpty() bool

IsEmpty answers: is the heap empty?

## Example ¶

Code:

heap := NewFloatFibHeap() fmt.Printf("Empty before insert? %v\n", heap.IsEmpty()) heap.Enqueue(SomeNumber) fmt.Printf("Empty after insert? %v\n", heap.IsEmpty())

Empty before insert? true Empty after insert? false

#### func (*FloatingFibonacciHeap) Merge ¶

func (heap *FloatingFibonacciHeap) Merge(other *FloatingFibonacciHeap) (FloatingFibonacciHeap, error)

Merge returns a new Fibonacci heap that contains all of the elements of the two heaps. Each of the input heaps is destructively modified by having all its elements removed. You can continue to use those heaps, but be aware that they will be empty after this call completes.

## Example ¶

Code:

heap1 := NewFloatFibHeap() heap2 := NewFloatFibHeap() heap1.Enqueue(SomeNumber) heap1.Enqueue(SomeLargerNumber) heap2.Enqueue(SomeSmallerNumber) min, _ := heap1.Min() fmt.Printf("Minimal element of heap 1: %v\n", min.Priority) min, _ = heap2.Min() fmt.Printf("Minimal element of heap 2: %v\n", min.Priority) heap, _ := heap1.Merge(&heap2) min, _ = heap.Min() fmt.Printf("Minimal element of merged heap: %v\n", min.Priority)

Minimal element of heap 1: 15.5 Minimal element of heap 2: -10.1 Minimal element of merged heap: -10.1

#### func (*FloatingFibonacciHeap) Min ¶

func (heap *FloatingFibonacciHeap) Min() (*Entry, error)

Min returns the minimum element in the heap

## Example ¶

Code:

heap := NewFloatFibHeap() heap.Enqueue(SomeNumber) heap.Enqueue(SomeLargerNumber) min, _ := heap.Min() fmt.Println(min.Priority)

15.5

#### func (*FloatingFibonacciHeap) Size ¶

func (heap *FloatingFibonacciHeap) Size() uint

Size gives the number of elements in the heap

## Example ¶

Code:

heap := NewFloatFibHeap() fmt.Printf("Size before insert: %v\n", heap.Size()) heap.Enqueue(SomeNumber) fmt.Printf("Size after insert: %v\n", heap.Size())

Size before insert: 0 Size after insert: 1