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

    Examples

    Constants

    This section is empty.

    Variables

    This section is empty.

    Functions

    This section is empty.

    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

                        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
                            

                            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

                              Source Files