Fibonacci Heap 
A Ruby implementation of the Fibonacci heap data structure ideal for use as a priority queue with Dijkstra's algorithm.
Current version: 0.2.0
Supported Ruby versions: 1.8.7, 1.9.2, 1.9.3, 2.0, 2.1, 2.2, 2.3
Installation
gem install fibonacci_heap -v '~> 0.1'
Or, in your Gemfile
:
gem 'fibonacci_heap', '~> 0.1'
Usage
require 'fibonacci_heap'
heap = FibonacciHeap::Heap.new
foo = FibonacciHeap::Node.new(1, 'foo')
bar = FibonacciHeap::Node.new(0, 'bar')
heap.insert(foo)
heap.insert(bar)
heap.pop
API Documentation
FibonacciHeap::Heap
A Fibonacci Heap data structure.
A "mergeable heap" that supports several operations that run in
constant amortized time. Structured as a collection of rooted trees
that are min-heap ordered.
FibonacciHeap::Heap.new
heap = FibonacciHeap::Heap.new
Return a new, empty FibonacciHeap::Heap
instance.
FibonacciHeap::Heap#n
heap = FibonacciHeap::Heap.new
heap.insert(FibonacciHeap::Node.new('foo'))
heap.n
heap.size
heap.length
Return the current number of nodes in the heap.
Aliased to size
and length
.
FibonacciHeap::Heap#empty?
heap = FibonacciHeap::Heap.new
heap.empty?
Returns whether or not the heap is empty.
FibonacciHeap::Heap#min
heap = FibonacciHeap::Heap.new
heap.insert(FibonacciHeap::Node.new(1))
heap.insert(FibonacciHeap::Node.new(2))
heap.min
Return the smallest FibonacciHeap::Node
node in the heap as determined by the node's key
.
Will return nil
if the heap is empty.
FibonacciHeap::Heap#insert(x[, k])
heap = FibonacciHeap::Heap.new
node = FibonacciHeap::Node.new(1, 'foo')
node2 = FibonacciHeap::Node.new(0, 'bar')
heap.insert(node)
heap.insert(bar, 100)
Insert the given FibonacciHeap::Node
x
into the heap with an optional key k
.
Defaults to using x
's existing key
for k
.
FibonacciHeap::Heap#concat(h2)
heap = FibonacciHeap::Heap.new
heap.insert(FibonacciHeap::Node.new(1, 'foo'))
heap2 = FibonacciHeap::Heap.new
heap2.insert(FibonacciHeap::Node.new(2, 'bar'))
heap3 = heap.concat(heap2)
heap3.pop
heap3.pop
Unite the given FibonacciHeap::Heap
h2
with this one in a new FibonacciHeap::Heap
.
As this will mutate both collections of rooted trees, attempting to use either the original heap or h2
after concat
has undefined behaviour.
FibonacciHeap::Heap#pop
heap = FibonacciHeap::Heap.new
heap.insert(FibonacciHeap::Node.new(1, 'foo'))
heap.pop
Remove and return the smallest FibonacciHeap::Node
from the heap.
FibonacciHeap::Heap#decrease_key(x, k)
heap = FibonacciHeap::Heap.new
node = FibonacciHeap::Node.new(1, 'foo')
heap.insert(node)
heap.decrease_key(node, 0)
Decrease the key of the given FibonacciHeap::Node
x
to the new given key k
.
The node must already be inserted into the heap and the key must be comparable.
Raises a FibonacciHeap::InvalidKeyError
if the new key is greater than the current key.
FibonacciHeap::Heap#delete(x)
heap = FibonacciHeap::Heap.new
node = FibonacciHeap::Node.new(1, 'foo')
heap.insert(node)
heap.delete(node)
Deletes the given FibonacciHeap::Node
x
from the heap.
The node must already be inserted into the heap.
FibonacciHeap::Heap#clear
heap = FibonacciHeap::Heap.new
heap.insert(FibonacciHeap::Node.new(1, 'foo'))
heap.clear
Remove all nodes from the heap, emptying it.
FibonacciHeap::Node
A single node in a FibonacciHeap::Heap
.
Used internally to form both min-heap ordered trees and circular, doubly linked lists.
FibonacciHeap::Node.new(key[, value])
node = FibonacciHeap::Node.new(1)
node = FibonacciHeap::Node.new(1, 'foo')
Return a new FibonacciHeap::Node
with the given key key
and an optional value value
.
Defaults to using the key
as the value.
FibonacciHeap::Node#key
node = FibonacciHeap::Node.new(1, 'foo')
node.key
Return the current key of the node.
FibonacciHeap::Node#value
node = FibonacciHeap::Node.new(1, 'foo')
node.value
Return the current value of the node.
FibonacciHeap::InvalidKeyError
Raised when attempting to decrease a key but the new key is greater than the current key.
References
License
Copyright Ā© 2018 Paul Mucur
Distributed under the MIT License.