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