class Graphos::BinaryHeap
Constants
- KeyVal
Public Class Methods
new(&compare)
click to toggle source
# File lib/graphos/binary_heap.rb, line 3 def initialize &compare @compare = compare @indexes = [] @keys = [] @values = [] end
Public Instance Methods
change(key, new_value)
click to toggle source
# File lib/graphos/binary_heap.rb, line 26 def change key, new_value if has_key? key @values[key] = new_value parent_val = @values[parent(@indexes[key])] move_up key heapify key end end
has_key?(key)
click to toggle source
# File lib/graphos/binary_heap.rb, line 16 def has_key? key @indexes[key] != nil end
next()
click to toggle source
# File lib/graphos/binary_heap.rb, line 20 def next if key = @keys.first key_val key end end
ordered()
click to toggle source
# File lib/graphos/binary_heap.rb, line 56 def ordered end
pop()
click to toggle source
# File lib/graphos/binary_heap.rb, line 35 def pop return nil if size == 0 result = key_val(@keys.first) @indexes[result.key] = nil @values[result.key] = nil last = @keys.pop if size > 0 @keys[0] = last @indexes[last] = 0 heapify last end result end
push(key, value)
click to toggle source
# File lib/graphos/binary_heap.rb, line 10 def push key, value if !has_key? key insert key, value end end
size()
click to toggle source
# File lib/graphos/binary_heap.rb, line 52 def size @keys.size end
Private Instance Methods
heapify(key)
click to toggle source
# File lib/graphos/binary_heap.rb, line 74 def heapify key left_key = @keys[left(@indexes[key])] right_key = @keys[right(@indexes[key])] return if !left_key && !right_key min_key = [key, left_key, right_key].select{|x| !!x}.sort do |x,y| @compare.call(key_val(x), key_val(y)) end.first return if min_key == key swap(@indexes[key], @indexes[min_key]) heapify key end
insert(key, value)
click to toggle source
# File lib/graphos/binary_heap.rb, line 66 def insert key, value @indexes[key] = @keys.size @keys.push key @values[key] = value move_up key end
key_val(key)
click to toggle source
# File lib/graphos/binary_heap.rb, line 62 def key_val key KeyVal.new(key, @values[key]) end
left(i)
click to toggle source
# File lib/graphos/binary_heap.rb, line 103 def left i 2*i + 1 end
move_up(key)
click to toggle source
# File lib/graphos/binary_heap.rb, line 90 def move_up key while( @indexes[key] != 0 && smaller(key_val(key), key_val(@keys[parent(@indexes[key])])) ) swap(parent(@indexes[key]), @indexes[key]) end end
parent(i)
click to toggle source
# File lib/graphos/binary_heap.rb, line 99 def parent i (i-1)/2 end
right(i)
click to toggle source
# File lib/graphos/binary_heap.rb, line 106 def right i 2*i + 2 end
smaller(a, b)
click to toggle source
# File lib/graphos/binary_heap.rb, line 115 def smaller a, b @compare.call(a,b) == -1 end
swap(a, b)
click to toggle source
# File lib/graphos/binary_heap.rb, line 110 def swap a, b @keys[a], @keys[b] = @keys[b], @keys[a] @indexes[@keys[a]], @indexes[@keys[b]] = @indexes[@keys[b]], @indexes[@keys[a]] end