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
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
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
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
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
Returns true if the heap is empty, false otherwise.
# File lib/containers/heap.rb 147 def empty? 148 @next.nil? 149 end
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
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
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
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
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
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
Return the number of elements in the heap.
# File lib/containers/heap.rb 19 def size 20 @size 21 end
Private Instance Methods
# 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
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
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
make node a child of a parent node
# File lib/containers/heap.rb 317 def link_nodes(child, parent) 318 # link the child's siblings 319 child.left.right = child.right 320 child.right.left = child.left 321 322 child.parent = parent 323 324 # if parent doesn't have children, make new child its only child 325 if parent.child.nil? 326 parent.child = child.right = child.left = child 327 else # otherwise insert new child into parent's children list 328 current_child = parent.child 329 child.left = current_child 330 child.right = current_child.right 331 current_child.right.left = child 332 current_child.right = child 333 end 334 parent.degree += 1 335 child.marked = false 336 end