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
Public Instance
Included modules
- Enumerable
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, line 38 def initialize(ary=[], &block) @compare_fn = block || lambda { |x, y| (x <=> y) == -1 } @next = nil @size = 0 @stored = {} ary.each { |n| push(n) } unless ary.empty? 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, line 262 def change_key(key, new_key, delete=false) return if @stored[key].nil? || @stored[key].empty? || (key == new_key) # Must maintain heap property raise "Changing this key would not maintain heap property!" unless (delete || @compare_fn[new_key, key]) node = @stored[key].shift if node node.key = new_key @stored[new_key] ||= [] @stored[new_key] << node parent = node.parent if parent # if heap property is violated if delete || @compare_fn[new_key, parent.key] cut(node, parent) cascading_cut(parent) end end if delete || @compare_fn[node.key, @next.key] @next = node end return [node.key, node.value] end nil end
Removes all elements from the heap, destructively.
Complexity: O(1)
# File lib/containers/heap.rb, line 143 def clear @next = nil @size = 0 @stored = {} nil 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, line 300 def delete(key) pop if change_key(key, nil, true) end
Returns true if the heap is empty, false otherwise.
# File lib/containers/heap.rb, line 154 def empty? @next.nil? 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, line 101 def has_key?(key) @stored[key] && !@stored[key].empty? ? true : false 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, line 170 def merge!(otherheap) raise ArgumentError, "Trying to merge a heap with something not a heap" unless otherheap.kind_of? Containers::Heap other_root = otherheap.instance_variable_get("@next") if other_root @stored = @stored.merge(otherheap.instance_variable_get("@stored")) { |key, a, b| (a << b).flatten } # Insert othernode's @next node to the left of current @next @next.left.right = other_root ol = other_root.left other_root.left = @next.left ol.right = @next @next.left = ol @next = other_root if @compare_fn[other_root.key, @next.key] end @size += otherheap.size 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, line 116 def next @next && @next.value 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, line 132 def next_key @next && @next.key 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, line 198 def pop return nil unless @next popped = @next if @size == 1 clear return popped.value end # Merge the popped's children into root node if @next.child @next.child.parent = nil # get rid of parent sibling = @next.child.right until sibling == @next.child sibling.parent = nil sibling = sibling.right end # Merge the children into the root. If @next is the only root node, make its child the @next node if @next.right == @next @next = @next.child else next_left, next_right = @next.left, @next.right current_child = @next.child @next.right.left = current_child @next.left.right = current_child.right current_child.right.left = next_left current_child.right = next_right @next = @next.right end else @next.left.right = @next.right @next.right.left = @next.left @next = @next.right end consolidate unless @stored[popped.key].delete(popped) raise "Couldn't delete node from stored nodes hash" end @size -= 1 popped.value 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, line 61 def push(key, value=key) raise ArgumentError, "Heap keys must not be nil." unless key node = Node.new(key, value) # Add new node to the left of the @next node if @next node.right = @next node.left = @next.left node.left.right = node @next.left = node if @compare_fn[key, @next.key] @next = node end else @next = node end @size += 1 arr = [] w = @next.right until w == @next do arr << w.value w = w.right end arr << @next.value @stored[key] ||= [] @stored[key] << node value end
Return the number of elements in the heap.
# File lib/containers/heap.rb, line 19 def size @size end