fibheap

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

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())

}

Output:

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
  • func (e EmptyHeapError) Error() string
• type Entry
• type FloatingFibonacciHeap
  • func NewFloatFibHeap() 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
  • func (e NilError) Error() string

Examples

• Package
• FloatingFibonacciHeap.DecreaseKey
• FloatingFibonacciHeap.Delete
• FloatingFibonacciHeap.DequeueMin
• FloatingFibonacciHeap.Enqueue
• FloatingFibonacciHeap.IsEmpty
• FloatingFibonacciHeap.Merge
• FloatingFibonacciHeap.Min
• FloatingFibonacciHeap.Size

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

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)

Output:

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

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)

Output:

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

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

Output:

Dequeueing minimal element: 15.5

func (*FloatingFibonacciHeap) Enqueue

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

Enqueue adds and element to the heap

Example

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

Output:

15.5

func (*FloatingFibonacciHeap) IsEmpty

func (heap *FloatingFibonacciHeap) IsEmpty() bool

IsEmpty answers: is the heap empty?

Example

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

Output:

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

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)

Output:

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

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

Output:

15.5

func (*FloatingFibonacciHeap) Size

func (heap *FloatingFibonacciHeap) Size() uint

Size gives the number of elements in the heap

Example

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

Output:

Size before insert: 0
Size after insert: 1

type NilError

type NilError string

NilError fires when a heap or entry is nil and an operation could not be completed for that reason. Its string holds additional data.

func (NilError) Error

func (e NilError) Error() string