A Ruby implementation of a Fibonacci heap

fibonacci_heap.rb

class CircularDoublyLinkedList
  include Enumerable

  class Node
    include Comparable

    attr_accessor :key, :next, :prev
    alias right next
    alias left prev

    def initialize(key)
      @key = key
      @next = self
      @prev = self
    end

    def <=>(other)
      key <=> other.key
    end
  end

  attr_accessor :sentinel

  def initialize
    @sentinel = Node.new(nil)
  end

  def empty?
    sentinel.next == sentinel
  end

  def insert(x)
    x.next = sentinel.next
    sentinel.next.prev = x
    sentinel.next = x
    x.prev = sentinel
  end

  def delete(x)
    x.prev.next = x.next
    x.next.prev = x.prev
  end

  def concat(list)
    list.sentinel.prev.next = sentinel.next
    sentinel.next.prev = list.sentinel.prev
    sentinel.next = list.sentinel.next
    list.sentinel.prev = sentinel
  end

  def each
    x = sentinel.next

    while x != sentinel
      yield x

      x = x.next
    end
  end
end

class FibonacciHeap
  InvalidKeyError = Class.new(StandardError)

  class Node < CircularDoublyLinkedList::Node
    attr_accessor :degree, :p, :mark, :children

    def initialize(*args)
      super

      @children = CircularDoublyLinkedList.new
    end
  end

  attr_accessor :n, :min, :root_list

  def initialize
    @n = 0
    @min = nil
  end

  def insert(x)
    x.degree = 0
    x.p = nil
    x.mark = false

    if !min
      self.root_list = CircularDoublyLinkedList.new
      root_list.insert(x)

      self.min = x
    else
      root_list.insert(x)
      if x.key < min.key
        self.min = x
      end
    end

    self.n += 1
  end

  def pop
    z = min

    if z
      z.children.each do |x|
        root_list.insert(x)
        x.p = nil
      end
      root_list.delete(z)
      if z == z.right
        self.min = nil
      else
        self.min = z.right
        consolidate
      end
      self.n += 1
    end

    z
  end

  def decrease_key(x, k)
    fail InvalidKeyError, 'new key is greater than current key' if k > x.key

    x.key = k
    y = x.p

    if y && x.key < y.key
      cut(x, y)
      cascading_cut(y)
    end

    if x.key < min.key
      self.min = x
    end
  end

  def delete(x)
    decrease_key(x, -Float::INFINITY)
    pop
  end

  private

  def consolidate
    a = Array.new(n)

    root_list.each do |w|
      x = w
      d = x.degree

      while a[d]
        y = a[d]
        if x.key > y.key
          x, y = y, x
        end
        link(y, x)
        a[d] = nil
        d += 1
      end

      a[d] = x
    end

    self.min = nil

    a.each do |root|
      next unless root

      if !min
        self.root_list = CircularDoublyLinkedList.new
        root_list.insert(root)
        self.min = root
      else
        root_list.insert(root)
        if root.key < min.key
          self.min = root
        end
      end
    end
  end

  def link(y, x)
    root_list.delete(y)
    x.children.insert(y)
    x.degree += 1
    y.p = x
    y.mark = false
  end

  def cut(x, y)
    y.children.delete(x)
    y.degree -= 1
    root_list.insert(x)
    x.p = nil
    x.mark = false
  end

  def cascading_cut(y)
    z = y.p
    if z
      if !y.mark
        y.mark = true
      else
        cut(y, z)
        cascading_cut(z)
      end
    end
  end
end

RSpec.describe CircularDoublyLinkedList::Node do
  describe '#next' do
    it 'is initialized to itself by default' do
      node = described_class.new('foo')

      expect(node.next).to eq(node)
    end
  end

  describe '#prev' do
    it 'is initialized to itself by default' do
      node = described_class.new('foo')

      expect(node.prev).to eq(node)
    end
  end
end

RSpec.describe CircularDoublyLinkedList do
  it 'is initialized with a sentinel nil' do
    list = described_class.new

    expect(list.sentinel).not_to be_nil
  end

  describe '#insert' do
    it 'inserts the node next to the sentinel' do
      list = described_class.new
      node = described_class::Node.new('foo')

      list.insert(node)

      expect(list.sentinel.next).to eq(node)
    end

    it 'sets the sentinel to the left of the new node' do
      list = described_class.new
      node = described_class::Node.new('foo')

      list.insert(node)

      expect(node.prev).to eq(list.sentinel)
    end

    it 'sets the next pointer on the new node' do
      list = described_class.new
      node = described_class::Node.new('foo')

      list.insert(node)

      expect(node.next).to eq(list.sentinel)
    end

    it 'inserts the node into a non-empty list' do
      list = described_class.new
      node = described_class::Node.new('foo')
      node2 = described_class::Node.new('bar')

      list.insert(node)
      list.insert(node2)

      expect(list.sentinel.next).to eq(node2)
      expect(list.sentinel.prev).to eq(node)
      expect(node2.prev).to eq(list.sentinel)
      expect(node2.next).to eq(node)
      expect(node.prev).to eq(node2)
      expect(node.next).to eq(list.sentinel)
    end
  end

  describe '#delete' do
    it 'removes a node from the list' do
      list = described_class.new
      node = described_class::Node.new('foo')

      list.insert(node)
      list.delete(node)

      expect(list.sentinel.next).to eq(list.sentinel)
      expect(list.sentinel.prev).to eq(list.sentinel)
    end
  end

  describe '#empty?' do
    it 'is true if the sentinel is connected to itself' do
      list = described_class.new

      expect(list).to be_empty
    end
  end

  describe '#each' do
    it 'yields nothing if the list is empty' do
      list = described_class.new

      expect { |b| list.each(&b) }.to yield_successive_args
    end

    it 'yields nodes' do
      list = described_class.new
      node = described_class::Node.new('foo')
      node2 = described_class::Node.new('bar')
      list.insert(node)
      list.insert(node2)

      expect { |b| list.each(&b) }.to yield_successive_args(node2, node)
    end
  end

  describe '#concat' do
    it 'combines two lists' do
      list = described_class.new
      list2 = described_class.new
      node = described_class::Node.new('foo')
      node2 = described_class::Node.new('bar')
      node3 = described_class::Node.new('baz')
      node4 = described_class::Node.new('quux')
      list.insert(node)
      list.insert(node2)
      list2.insert(node3)
      list2.insert(node4)

      list.concat(list2)

      expect(list.to_a).to contain_exactly(node, node2, node3, node4)
    end
  end
end

RSpec.describe FibonacciHeap do
  it 'initializes n to 0' do
    heap = described_class.new

    expect(heap.n).to be_zero
  end

  it 'initializes min to nil' do
    heap = described_class.new

    expect(heap.min).to be_nil
  end

  describe '#insert' do
    it 'adds the node to the root list' do
      heap = described_class.new
      node = described_class::Node.new('foo')

      heap.insert(node)

      expect(heap.root_list).to include(node)
    end

    it 'sets the node to min for an empty heap' do
      heap = described_class.new
      node = described_class::Node.new('foo')

      heap.insert(node)

      expect(heap.min).to eq(node)
    end

    it 'does not override min if a smaller node already exists' do
      heap = described_class.new
      node = described_class::Node.new('foo')
      node2 = described_class::Node.new('bar')

      heap.insert(node2)
      heap.insert(node)

      expect(heap.min).to eq(node2)
    end
  end

  describe '#pop' do
    it 'returns nil if the heap is empty' do
      heap = described_class.new

      expect(heap.pop).to be_nil
    end

    it 'returns the smallest node' do
      heap = described_class.new
      node = described_class::Node.new(1)
      node2 = described_class::Node.new(2)

      heap.insert(node)
      heap.insert(node2)

      expect(heap.pop).to eq(node)
    end

    it 'removes the smallest node from the heap' do
      heap = described_class.new
      node = described_class::Node.new(1)
      node2 = described_class::Node.new(2)

      heap.insert(node)
      heap.insert(node2)
      heap.pop

      expect(heap.root_list).to contain_exactly(node2)
    end

    it 'works with more than two nodes' do
      heap = described_class.new
      node = described_class::Node.new(-1)
      heap.insert(node)

      25.times do |i|
        heap.insert(described_class::Node.new(i))
      end

      expect(heap.pop).to eq(node)
    end
  end

  describe '#decrease_key' do
    it 'raises an error if the key is greater than the existing value' do
      heap = described_class.new
      node = described_class::Node.new(1)
      heap.insert(node)

      expect { heap.decrease_key(node, 4) }.to raise_error(FibonacciHeap::InvalidKeyError)
    end

    it 'decreases the key of the node' do
      heap = described_class.new
      node = described_class::Node.new(2)
      node2 = described_class::Node.new(3)
      heap.insert(node)
      heap.insert(node2)

      heap.decrease_key(node2, 1)

      expect(node2.key).to eq(1)
    end

    it 'updates the min of the heap' do
      heap = described_class.new
      node = described_class::Node.new(2)
      node2 = described_class::Node.new(3)
      heap.insert(node)
      heap.insert(node2)

      heap.decrease_key(node2, 1)

      expect(heap.min).to eq(node2)
    end
  end

  describe '#delete' do
    it 'removes the node from the heap' do
      heap = described_class.new
      node = described_class::Node.new(2)
      node2 = described_class::Node.new(1)
      heap.insert(node)
      heap.insert(node2)

      heap.delete(node)

      expect(heap.root_list).not_to include(node)
    end
  end
end