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

gem install fibonacci_heap -v '~> 0.2'

Or, in your Gemfile:

gem 'fibonacci_heap', '~> 0.2'

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">

• FibonacciHeap::Heap
  • .new
  • #n
  • #size
  • #length
  • #empty?
  • #min
  • #insert(x[, k])
  • #concat(h2)
  • #pop
  • #decrease_key(x, k)
  • #delete(x)
  • #clear
• FibonacciHeap::Node
  • new(key[, value])
  • key
  • value
• FibonacciHeap::InvalidKeyError

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.

heap = FibonacciHeap::Heap.new
#=> #<FibonacciHeap n=0 min=nil>

Return a new, empty FibonacciHeap::Heap instance.

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.

heap = FibonacciHeap::Heap.new
heap.empty?
#=> true

Returns whether or not the heap is empty.

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.

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.

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.

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.

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.

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.

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.

A single node in a FibonacciHeap::Heap.

Used internally to form both min-heap ordered trees and circular, doubly linked lists.

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.

node = FibonacciHeap::Node.new(1, 'foo')
node.key
#=> 1

Return the current key of the node.

node = FibonacciHeap::Node.new(1, 'foo')
node.value
#=> "foo"

Return the current value of the node.

Raised when attempting to decrease a key but the new key is greater than the current key.

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 Nodes themselves, it then makes the passing of Nodes to methods such as insert, delete and decrease_key more consistent.

• Cormen, T. H., Leiserson, C. E., Rivest, R. L. & Stein, C., Introduction to Algorithms, Third Edition.

Copyright © 2018 Paul Mucur

Distributed under the MIT License.