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
255 def change_key(key, new_key, delete=false)
256   return if @stored[key].nil? || @stored[key].empty? || (key == new_key)
257   
258   # Must maintain heap property
259   raise "Changing this key would not maintain heap property!" unless (delete || @compare_fn[new_key, key])
260   node = @stored[key].shift
261   if node
262     node.key = new_key
263     @stored[new_key] ||= []
264     @stored[new_key] << node
265     parent = node.parent
266     if parent
267       # if heap property is violated
268       if delete || @compare_fn[new_key, parent.key]
269         cut(node, parent)
270         cascading_cut(parent)
271       end
272     end
273     if delete || @compare_fn[node.key, @next.key]
274       @next = node
275     end
276     return [node.key, node.value]
277   end
278   nil
279 end
clear → nil click to toggle source

Removes all elements from the heap, destructively.

Complexity: O(1)

    # File lib/containers/heap.rb
136 def clear
137   @next = nil
138   @size = 0
139   @stored = {}
140   nil
141 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
293 def delete(key)
294   pop if change_key(key, nil, true)
295 end
empty? → true or false click to toggle source

Returns true if the heap is empty, false otherwise.

    # File lib/containers/heap.rb
147 def empty?
148   @next.nil?
149 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
94 def has_key?(key)
95   @stored[key] && !@stored[key].empty? ? true : false
96 end
length
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
163 def merge!(otherheap)
164   raise ArgumentError, "Trying to merge a heap with something not a heap" unless otherheap.kind_of? Containers::Heap
165   other_root = otherheap.instance_variable_get("@next")
166   if other_root
167     @stored = @stored.merge(otherheap.instance_variable_get("@stored")) { |key, a, b| (a << b).flatten }
168     # Insert othernode's @next node to the left of current @next
169     @next.left.right = other_root
170     ol = other_root.left
171     other_root.left = @next.left
172     ol.right = @next
173     @next.left = ol
174     
175     @next = other_root if @compare_fn[other_root.key, @next.key]
176   end
177   @size += otherheap.size
178 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
109 def next
110   @next && @next.value
111 end
next!
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
125 def next_key
126   @next && @next.key
127 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
191 def pop
192   return nil unless @next
193   popped = @next
194   if @size == 1
195     clear
196     return popped.value
197   end
198   # Merge the popped's children into root node
199   if @next.child
200     @next.child.parent = nil
201     
202     # get rid of parent
203     sibling = @next.child.right
204     until sibling == @next.child
205       sibling.parent = nil
206       sibling = sibling.right
207     end
208     
209     # Merge the children into the root. If @next is the only root node, make its child the @next node
210     if @next.right == @next
211       @next = @next.child
212     else
213       next_left, next_right = @next.left, @next.right
214       current_child = @next.child
215       @next.right.left = current_child
216       @next.left.right = current_child.right
217       current_child.right.left = next_left
218       current_child.right = next_right
219       @next = @next.right
220     end
221   else
222     @next.left.right = @next.right
223     @next.right.left = @next.left
224     @next = @next.right
225   end
226   consolidate
227   
228   unless @stored[popped.key].delete(popped)
229     raise "Couldn't delete node from stored nodes hash" 
230   end
231   @size -= 1
232   
233   popped.value
234 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   @stored[key] ||= []
79   @stored[key] << node
80   value
81 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
379 def cascading_cut(node)
380   p = node.parent
381   if p
382     if node.marked?
383       cut(node, p)
384       cascading_cut(p)
385     else
386       node.marked = true
387     end
388   end
389 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
340 def consolidate
341   roots = []
342   root = @next
343   min = root
344   # find the nodes in the list
345   loop do
346     roots << root
347     root = root.right
348     break if root == @next
349   end
350   degrees = []
351   roots.each do |root|
352     min = root if @compare_fn[root.key, min.key]
353     # check if we need to merge
354     if degrees[root.degree].nil?  # no other node with the same degree
355       degrees[root.degree] = root
356       next
357     else  # there is another node with the same degree, consolidate them
358       degree = root.degree
359       until degrees[degree].nil? do
360         other_root_with_degree = degrees[degree]
361         if @compare_fn[root.key, other_root_with_degree.key]  # determine which node is the parent, which one is the child
362           smaller, larger = root, other_root_with_degree
363         else
364           smaller, larger = other_root_with_degree, root
365         end
366         link_nodes(larger, smaller)
367         degrees[degree] = nil
368         root = smaller
369         degree += 1
370       end
371       degrees[degree] = root
372       min = root if min.key == root.key # this fixes a bug with duplicate keys not being in the right order
373     end
374   end
375   @next = min
376 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
393 def cut(x, y)
394   x.left.right = x.right
395   x.right.left = x.left
396   y.degree -= 1
397   if (y.degree == 0)
398     y.child = nil
399   elsif (y.child == x)
400     y.child = x.right
401   end
402   x.right = @next
403   x.left = @next.left
404   @next.left = x
405   x.left.right = x
406   x.parent = nil
407   x.marked = false
408 end