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.2'
Or, in your Gemfile
:
gem 'fibonacci_heap', '~> 0.2'
Usage
require 'fibonacci_heap'
heap = FibonacciHeap::Heap.new
foo = FibonacciHeap::Node.new(1, 'foo')
bar = FibonacciHeap::Node.new(0, 'bar')
baz = FibonacciHeap::Node.new(2, 'baz')
heap.insert(foo)
heap.insert(bar)
heap.insert(baz)
heap.pop
#=> #<FibonacciHeap::Node key=0 value="bar">
heap.decrease_key(baz, 0)
heap.pop
#=> #<FibonacciHeap::Node key=0 value="baz">
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 value=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)
#=> #<FibonacciHeap::Node key=1 value="foo">
heap.insert(node2, 100)
#=> #<FibonacciHeap::Node key=100 value="bar">
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.
PQueue or algorithms' Containers::PriorityQueue
?
How is this different from PQueue and Containers::PriorityQueue
are also implementations of a Priority Queue but my specific use-case required the ability to alter the priority (really, the key
) of arbitrary nodes after insertion. PQueue allows you to customise the comparison of nodes but this is only done at insertion time. Similarly, Containers::PriorityQueue
does not allow you to alter the priority of a specific node (you can delete a single node by its priority but any other node with the same priority might be deleted instead).
Furthermore, as the reference text for my implementation often relies on the user having references to the nodes in the heap (e.g. for decrease_key
and delete
), I wanted to make the notion of the Node
explicit in the API. By having the user initialize Node
s themselves, it then makes the passing of Node
s to methods such as insert
, delete
and decrease_key
more consistent.
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.