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

#clear ⇒ Object

Remove all nodes from the heap, emptying it.



158
159
160
161
162
163
164
 
# File 'lib/fibonacci_heap/heap.rb', line 158

def clear
  self.root_list = CircularDoublyLinkedList.new
  self.min = nil
  self.n = 0

  self
end

#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 after uniting has undefined behaviour.

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



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

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

  h.root_list = CircularDoublyLinkedList.new
  h.root_list.concat(root_list) unless empty?
  h.root_list.concat(h2.root_list) unless h2.empty?

  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:



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

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.



152
153
154
155
 
# File 'lib/fibonacci_heap/heap.rb', line 152

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

#empty? ⇒ Boolean

Return whether or not this heap is empty.

Returns:

  • (Boolean) 


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

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.



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

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 



166
167
168
 
# File 'lib/fibonacci_heap/heap.rb', line 166

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.



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
 
# File 'lib/fibonacci_heap/heap.rb', line 93

def pop
  z = min
  return unless 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)

  # Was z the only node on the root list?
  if z.right == z.left
    self.min = nil
  else
    # Set min to another root
    self.min = root_list.head

    consolidate
  end

  self.n -= 1

  z
end