Class Containers::Heap

  1. lib/containers/heap.rb
Parent: Object

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.

Methods

public class

  1. new

public instance

  1. <<
  2. change_key
  3. clear
  4. delete
  5. empty?
  6. has_key?
  7. length
  8. merge!
  9. next
  10. next!
  11. pop
  12. push
  13. size

Included modules

  1. Enumerable

Public class methods

Heap.new(optional_array) { |x, y| optional_comparison_fn } → new_heap

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.

[show source]
    # File lib/containers/heap.rb, line 38
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

<< (key, value=key)

Alias for push

change_key(key, new_key) → [new_key, value]
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
[show source]
     # File lib/containers/heap.rb, line 246
246:   def change_key(key, new_key, delete=false)
247:     return if @stored[key].nil? || @stored[key].empty? || (key == new_key)
248:     
249:     # Must maintain heap property
250:     raise "Changing this key would not maintain heap property!" unless (delete || @compare_fn[new_key, key])
251:     node = @stored[key].shift
252:     if node
253:       node.key = new_key
254:       @stored[new_key] ||= []
255:       @stored[new_key] << node
256:       parent = node.parent
257:       if parent
258:         # if heap property is violated
259:         if delete || @compare_fn[new_key, parent.key]
260:           cut(node, parent)
261:           cascading_cut(parent)
262:         end
263:       end
264:       if delete || @compare_fn[node.key, @next.key]
265:         @next = node
266:       end
267:       return [node.key, node.value]
268:     end
269:     nil
270:   end
clear → nil

Removes all elements from the heap, destructively.

Complexity: O(1)

[show source]
     # File lib/containers/heap.rb, line 127
127:   def clear
128:     @next = nil
129:     @size = 0
130:     @stored = {}
131:     nil
132:   end
delete(key) → value
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
[show source]
     # File lib/containers/heap.rb, line 284
284:   def delete(key)
285:     pop if change_key(key, nil, true)
286:   end
empty? → true or false

Returns true if the heap is empty, false otherwise.

[show source]
     # File lib/containers/heap.rb, line 138
138:   def empty?
139:     @next.nil?
140:   end
has_key?(key) → true or false

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
[show source]
     # File lib/containers/heap.rb, line 101
101:   def has_key?(key)
102:     @stored[key] && !@stored[key].empty? ? true : false
103:   end
length ()

Alias for size

merge!(otherheap) → merged_heap

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
[show source]
     # File lib/containers/heap.rb, line 154
154:   def merge!(otherheap)
155:     raise ArgumentError, "Trying to merge a heap with something not a heap" unless otherheap.kind_of? Containers::Heap
156:     other_root = otherheap.instance_variable_get("@next")
157:     if other_root
158:       @stored = @stored.merge(otherheap.instance_variable_get("@stored")) { |key, a, b| (a << b).flatten }
159:       # Insert othernode's @next node to the left of current @next
160:       @next.left.right = other_root
161:       ol = other_root.left
162:       other_root.left = @next.left
163:       ol.right = @next
164:       @next.left = ol
165:       
166:       @next = other_root if @compare_fn[other_root.key, @next.key]
167:     end
168:     @size += otherheap.size
169:   end
next → value
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
[show source]
     # File lib/containers/heap.rb, line 116
116:   def next
117:     @next && @next.value
118:   end
next! ()

Alias for pop

pop → value
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
[show source]
     # File lib/containers/heap.rb, line 182
182:   def pop
183:     return nil unless @next
184:     popped = @next
185:     if @size == 1
186:       clear
187:       return popped.value
188:     end
189:     # Merge the popped's children into root node
190:     if @next.child
191:       @next.child.parent = nil
192:       
193:       # get rid of parent
194:       sibling = @next.child.right
195:       until sibling == @next.child
196:         sibling.parent = nil
197:         sibling = sibling.right
198:       end
199:       
200:       # Merge the children into the root. If @next is the only root node, make its child the @next node
201:       if @next.right == @next
202:         @next = @next.child
203:       else
204:         next_left, next_right = @next.left, @next.right
205:         current_child = @next.child
206:         @next.right.left = current_child
207:         @next.left.right = current_child.right
208:         current_child.right.left = next_left
209:         current_child.right = next_right
210:         @next = @next.right
211:       end
212:     else
213:       @next.left.right = @next.right
214:       @next.right.left = @next.left
215:       @next = @next.right
216:     end
217:     consolidate
218:     
219:     unless @stored[popped.key].delete(popped)
220:       raise "Couldn't delete node from stored nodes hash" 
221:     end
222:     @size -= 1
223:     
224:     popped.value
225:   end
push(key, value) → value
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
[show source]
    # File lib/containers/heap.rb, line 61
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
size → int

Return the number of elements in the heap.

[show source]
    # File lib/containers/heap.rb, line 19
19:   def size
20:     @size
21:   end