class Containers::Heap

A Heap is a container that satisfies the heap property that nodes are always smaller in value than their parent node.

The Containers::Heap class is flexible and upon initialization, takes an optional block that determines how the items are ordered. Two versions that are included are the Containers::MaxHeap and Containers::MinHeap that return the largest and smallest items on each invocation, respectively.

This library implements a Fibonacci heap, which allows O(1) complexity for most methods.

Public Class Methods

new(optional_array) { |x, y| optional_comparison_fn } → new_heap click to toggle source

If an optional array is passed, the entries in the array are inserted into the heap with equal key and value fields. Also, an optional block can be passed to define the function that maintains heap property. For example, a min-heap can be created with:

minheap = Heap.new { |x, y| (x <=> y) == -1 }
minheap.push(6)
minheap.push(10)
minheap.pop #=> 6

Thus, smaller elements will be parent nodes. The heap defaults to a min-heap if no block is given.

   # File lib/containers/heap.rb
38 def initialize(ary=[], &block)
39   @compare_fn = block || lambda { |x, y| (x <=> y) == -1 }
40   @next = nil
41   @size = 0
42   @stored = {}
43   
44   ary.each { |n| push(n) } unless ary.empty?
45 end

Public Instance Methods

Alias for: push
change_key(key, new_key) → [new_key, value] click to toggle source
change_key(key, new_key) → nil

Changes the key from one to another. Doing so must not violate the heap property or an exception will be raised. If the key is found, an array containing the new key and value pair is returned, otherwise nil is returned.

In the case of duplicate keys, an arbitrary key is changed. This will be investigated more in the future.

Complexity: amortized O(1)

minheap = MinHeap.new([1, 2])
minheap.change_key(2, 3) #=> raise error since we can't increase the value in a min-heap
minheap.change_key(2, 0) #=> [0, 2]
minheap.pop #=> 2
minheap.pop #=> 1
    # File lib/containers/heap.rb
259 def change_key(key, new_key, delete=false)
260   return if @stored[key].nil? || @stored[key].empty? || (key == new_key)
261   
262   # Must maintain heap property
263   raise "Changing this key would not maintain heap property!" unless (delete || @compare_fn[new_key, key])
264   node = @stored[key].shift
265   if node
266     node.key = new_key
267     @stored[new_key] ||= []
268     @stored[new_key] << node
269     parent = node.parent
270     if parent
271       # if heap property is violated
272       if delete || @compare_fn[new_key, parent.key]
273         cut(node, parent)
274         cascading_cut(parent)
275       end
276     end
277     if delete || @compare_fn[node.key, @next.key]
278       @next = node
279     end
280     return [node.key, node.value]
281   end
282   nil
283 end
clear → nil click to toggle source

Removes all elements from the heap, destructively.

Complexity: O(1)

    # File lib/containers/heap.rb
143 def clear
144   @next = nil
145   @size = 0
146   @stored = {}
147   nil
148 end
delete(key) → value click to toggle source
delete(key) → nil

Deletes the item with associated key and returns it. nil is returned if the key is not found. In the case of nodes with duplicate keys, an arbitrary one is deleted.

Complexity: amortized O(log n)

minheap = MinHeap.new([1, 2])
minheap.delete(1) #=> 1
minheap.size #=> 1
    # File lib/containers/heap.rb
297 def delete(key)
298   pop if change_key(key, nil, true)
299 end
empty? → true or false click to toggle source

Returns true if the heap is empty, false otherwise.

    # File lib/containers/heap.rb
154 def empty?
155   @next.nil?
156 end
has_key?(key) → true or false click to toggle source

Returns true if heap contains the key.

Complexity: O(1)

minheap = MinHeap.new([1, 2])
minheap.has_key?(2) #=> true
minheap.has_key?(4) #=> false
    # File lib/containers/heap.rb
101 def has_key?(key)
102   @stored[key] && !@stored[key].empty? ? true : false
103 end
Alias for: size
merge!(otherheap) → merged_heap click to toggle source

Does a shallow merge of all the nodes in the other heap.

Complexity: O(1)

heap = MinHeap.new([5, 6, 7, 8])
otherheap = MinHeap.new([1, 2, 3, 4])
heap.merge!(otherheap)
heap.size #=> 8
heap.pop #=> 1
    # File lib/containers/heap.rb
170 def merge!(otherheap)
171   raise ArgumentError, "Trying to merge a heap with something not a heap" unless otherheap.kind_of? Containers::Heap
172   other_root = otherheap.instance_variable_get("@next")
173   if other_root
174     @stored = @stored.merge(otherheap.instance_variable_get("@stored")) { |key, a, b| (a << b).flatten }
175     # Insert othernode's @next node to the left of current @next
176     @next.left.right = other_root
177     ol = other_root.left
178     other_root.left = @next.left
179     ol.right = @next
180     @next.left = ol
181     
182     @next = other_root if @compare_fn[other_root.key, @next.key]
183   end
184   @size += otherheap.size
185 end
next → value click to toggle source
next → nil

Returns the value of the next item in heap order, but does not remove it.

Complexity: O(1)

minheap = MinHeap.new([1, 2])
minheap.next #=> 1
minheap.size #=> 2
    # File lib/containers/heap.rb
116 def next
117   @next && @next.value
118 end
Alias for: pop
next_key → key click to toggle source
next_key → nil

Returns the key associated with the next item in heap order, but does not remove the value.

Complexity: O(1)

minheap = MinHeap.new
minheap.push(1, :a)
minheap.next_key #=> 1
    # File lib/containers/heap.rb
132 def next_key
133   @next && @next.key
134 end
pop → value click to toggle source
pop → nil

Returns the value of the next item in heap order and removes it from the heap.

Complexity: O(1)

minheap = MinHeap.new([1, 2])
minheap.pop #=> 1
minheap.size #=> 1
    # File lib/containers/heap.rb
198 def pop
199   return nil unless @next
200   popped = @next
201   if @size == 1
202     clear
203     return popped.value
204   end
205   # Merge the popped's children into root node
206   if @next.child
207     @next.child.parent = nil
208     
209     # get rid of parent
210     sibling = @next.child.right
211     until sibling == @next.child
212       sibling.parent = nil
213       sibling = sibling.right
214     end
215     
216     # Merge the children into the root. If @next is the only root node, make its child the @next node
217     if @next.right == @next
218       @next = @next.child
219     else
220       next_left, next_right = @next.left, @next.right
221       current_child = @next.child
222       @next.right.left = current_child
223       @next.left.right = current_child.right
224       current_child.right.left = next_left
225       current_child.right = next_right
226       @next = @next.right
227     end
228   else
229     @next.left.right = @next.right
230     @next.right.left = @next.left
231     @next = @next.right
232   end
233   consolidate
234   
235   @size -= 1
236   
237   popped.value
238 end
Also aliased as: next!
push(key, value) → value click to toggle source
push(value) → value

Inserts an item with a given key into the heap. If only one parameter is given, the key is set to the value.

Complexity: O(1)

heap = MinHeap.new
heap.push(1, "Cat")
heap.push(2)
heap.pop #=> "Cat"
heap.pop #=> 2
   # File lib/containers/heap.rb
61 def push(key, value=key)
62   raise ArgumentError, "Heap keys must not be nil." unless key
63   node = Node.new(key, value)
64   # Add new node to the left of the @next node
65   if @next
66     node.right = @next
67     node.left = @next.left
68     node.left.right = node
69     @next.left = node
70     if @compare_fn[key, @next.key]
71       @next = node
72     end
73   else
74     @next = node
75   end
76   @size += 1
77   
78   arr = []
79   w = @next.right
80   until w == @next do
81     arr << w.value
82     w = w.right
83   end
84   arr << @next.value
85   @stored[key] ||= []
86   @stored[key] << node
87   value
88 end
Also aliased as: <<
size → int click to toggle source

Return the number of elements in the heap.

   # File lib/containers/heap.rb
19 def size
20   @size
21 end
Also aliased as: length

Private Instance Methods

cascading_cut(node) click to toggle source
    # File lib/containers/heap.rb
383 def cascading_cut(node)
384   p = node.parent
385   if p
386     if node.marked?
387       cut(node, p)
388       cascading_cut(p)
389     else
390       node.marked = true
391     end
392   end
393 end
consolidate() click to toggle source

Makes sure the structure does not contain nodes in the root list with equal degrees

    # File lib/containers/heap.rb
344 def consolidate
345   roots = []
346   root = @next
347   min = root
348   # find the nodes in the list
349   loop do
350     roots << root
351     root = root.right
352     break if root == @next
353   end
354   degrees = []
355   roots.each do |root|
356     min = root if @compare_fn[root.key, min.key]
357     # check if we need to merge
358     if degrees[root.degree].nil?  # no other node with the same degree
359       degrees[root.degree] = root
360       next
361     else  # there is another node with the same degree, consolidate them
362       degree = root.degree
363       until degrees[degree].nil? do
364         other_root_with_degree = degrees[degree]
365         if @compare_fn[root.key, other_root_with_degree.key]  # determine which node is the parent, which one is the child
366           smaller, larger = root, other_root_with_degree
367         else
368           smaller, larger = other_root_with_degree, root
369         end
370         link_nodes(larger, smaller)
371         degrees[degree] = nil
372         root = smaller
373         degree += 1
374       end
375       degrees[degree] = root
376       min = root if min.key == root.key # this fixes a bug with duplicate keys not being in the right order
377     end
378   end
379   @next = min
380 end
cut(x, y) click to toggle source

remove x from y's children and add x to the root list

    # File lib/containers/heap.rb
397 def cut(x, y)
398   x.left.right = x.right
399   x.right.left = x.left
400   y.degree -= 1
401   if (y.degree == 0)
402     y.child = nil
403   elsif (y.child == x)
404     y.child = x.right
405   end
406   x.right = @next
407   x.left = @next.left
408   @next.left = x
409   x.left.right = x
410   x.parent = nil
411   x.marked = false
412 end