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')
= FibonacciHeap::Node.new(0, 'bar')
heap.insert(foo)
heap.insert()
heap.pop
#=> #<FibonacciHeap::Node key=0 value="bar">
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
#=> #<FibonacciHeap n=0 min=nil>
Return a new, empty FibonacciHeap::Heap
instance.
FibonacciHeap::Heap#n
heap = FibonacciHeap::Heap.new
heap.insert(FibonacciHeap::Node.new('foo'))
heap.n
#=> 1
heap.size
#=> 1
heap.length
#=> 1
Return the current number of nodes in the heap.
Aliased to size
and length
.
FibonacciHeap::Heap#empty?
heap = FibonacciHeap::Heap.new
heap.empty?
#=> true
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
#=> #<FibonacciHeap::Node key=1 ...>
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(, 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)
#=> #<FibonacciHeap::Heap n=2 min=#<FibonacciHeap::Node key=1 value="foo">>
heap3.pop
#=> #<FibonacciHeap::Node key=1 value="foo" ...>
heap3.pop
#=> #<FibonacciHeap::Node key=2 value="bar" ...>
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
#=> #<FibonacciHeap::Node key=1 value="foo" ...>
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)
#=> #<FibonacciHeap::Node key=0 value="foo">
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)
#=> #<FibonacciHeap::Node key=-Infinity value="foo">
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
#=> #<FibonacciHeap::Heap n=0 min=nil>
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)
#=> #<FibonacciHeap::Node key=1 value=1>
node = FibonacciHeap::Node.new(1, 'foo')
#=> #<FibonacciHeap::Node key=1 value="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
#=> 1
Return the current key of the node.
FibonacciHeap::Node#value
node = FibonacciHeap::Node.new(1, 'foo')
node.value
#=> "foo"
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
- Cormen, T. H., Leiserson, C. E., Rivest, R. L. & Stein, C., Introduction to Algorithms, Third Edition.
License
Copyright © 2018 Paul Mucur
Distributed under the MIT License.