Class: FibonacciHeap::Heap

Inherits:
Object
  • Object
show all
Defined in:
lib/fibonacci_heap/heap.rb

Overview

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.

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize ⇒ Heap

Return a new, empty Fibonacci heap.



24
25
26
27
 
# File 'lib/fibonacci_heap/heap.rb', line 24

def initialize
  @n = 0
  @min = nil
end

Instance Attribute Details

#min ⇒ Object

Return the smallest node in the heap.



18
19
20
 
# File 'lib/fibonacci_heap/heap.rb', line 18

def min
  @min
end

#n ⇒ Object Also known as: size, length

Return the current number of nodes in the heap.



13
14
15
 
# File 'lib/fibonacci_heap/heap.rb', line 13

def n
  @n
end

#root_list ⇒ Object

Return the root list of the heap.



21
22
23
 
# File 'lib/fibonacci_heap/heap.rb', line 21

def root_list
  @root_list
end

Instance Method Details

#concat(h2) ⇒ Object

Unite the given Fibonacci heap into this one, returning a new heap.

Note that uniting the heaps will mutate their root lists, destroying them both so attempting to use them has undefined behaviour.

Corresponds to the Fib-Heap-Union(H1, H2) procedure.



71
72
73
74
75
76
77
78
79
80
81
82
83
 
# File 'lib/fibonacci_heap/heap.rb', line 71

def concat(h2)
  h = self.class.new
  h.min = min

  h.root_list = root_list
  h.root_list.concat(h2.root_list)

  h.min = h2.min if !min || (h2.min && h2.min.key < min.key)

  h.n = n + h2.n

  h
end

#decrease_key(x, k) ⇒ Object

Decrease the key of a given node to a new given key.

The node must be compatible with a FibonacciHeap::Node and have been inserted in the heap already. The key must be comparable.

Raises an InvalidKeyError if the new key is greater than the current key.

Corresponds to the Fib-Heap-Decrease-Key(H, x, k) procedure.

Raises:



132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
 
# File 'lib/fibonacci_heap/heap.rb', line 132

def decrease_key(x, k)
  raise InvalidKeyError, "new key #{k} is greater than current key #{x.key}" if k > x.key

  x.key = k
  y = x.p

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

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

  x
end

#delete(x) ⇒ Object

Delete a node from the heap.

The given node must be compatible with a FibonacciHeap::Node and have been inserted in the heap already.

Corresponds to the Fib-Heap-Delete(H, x) procedure.



154
155
156
157
 
# File 'lib/fibonacci_heap/heap.rb', line 154

def delete(x)
  decrease_key(x, -1.0 / 0.0)
  pop
end

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


29
30
31
 
# File 'lib/fibonacci_heap/heap.rb', line 29

def empty?
  n.zero?
end

#insert(x, k = x.key) ⇒ Object

Insert a new node with an optional key into the heap.

The node must be compatible with a FibonacciHeap::Node.

Defaults to using the existing key of the node.

Corresponds to the Fib-Heap-Insert(H, x) procedure.



40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
 
# File 'lib/fibonacci_heap/heap.rb', line 40

def insert(x, k = x.key)
  x.degree = 0
  x.p = nil
  x.child_list = CircularDoublyLinkedList.new
  x.mark = false
  x.key = k

  if !min
    # Create a root list for H containing just x
    self.root_list = CircularDoublyLinkedList.new
    root_list.insert(x)

    self.min = x
  else
    # Insert x into H's root list
    root_list.insert(x)

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

  self.n += 1

  x
end

#inspect ⇒ Object 



159
160
161
 
# File 'lib/fibonacci_heap/heap.rb', line 159

def inspect
  %(#<#{self.class} n=#{n} min=#{min.inspect}>)
end

#pop ⇒ Object

Remove and return the minimum node from the heap.

After extracting the minimum node, the heap will consolidate its internal trees.

Corresponds to the Fib-Heap-Extract-Min(H) procedure.



91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
 
# File 'lib/fibonacci_heap/heap.rb', line 91

def pop
  z = min

  if z
    # For each child x of z
    z.child_list.each do |x|

      # Add x to the root list of H
      root_list.insert(x)
      x.p = nil
    end

    # Remove z from the root list of H
    root_list.delete(z)

    # Is z the only node on the root list?
    if z.right == z.left
      # Empty the heap
      self.min = nil
      self.root_list = CircularDoublyLinkedList.new
    else
      # Set min to another root
      self.min = root_list.head

      consolidate
    end

    self.n -= 1
  end

  z
end