class BinaryMinHeap

Attributes

prc[RW]
store[RW]

Public Class Methods

child_indices(len, parent_idx) click to toggle source
# File lib/simms_structures/heap.rb, line 32
def self.child_indices(len, parent_idx)
  first_child_idx = ( parent_idx * 2 ) + 1
  second_child_idx = ( parent_idx * 2 ) + 2

  [first_child_idx, second_child_idx].select do |idx|
    idx < len && idx > -1
  end
end
heapify_down(array, parent_idx, len = array.length, &prc) click to toggle source
# File lib/simms_structures/heap.rb, line 46
def self.heapify_down(array, parent_idx, len = array.length, &prc)
  prc ||= Proc.new { |a, b| a <=> b }

  child_idxs = BinaryMinHeap.child_indices(len, parent_idx)
  if child_idxs.empty?
    return array
  elsif child_idxs.count == 1
    target_child = child_idxs.first
  else
    if prc.call(array[child_idxs.first], array[child_idxs.last]) > -1
      target_child = child_idxs.last
    else
      target_child = child_idxs.first
    end
  end

  if prc.call(array[parent_idx], array[target_child]) > -1
    array[parent_idx], array[target_child] = array[target_child], array[parent_idx]
    BinaryMinHeap.heapify_down(array, target_child, len, &prc)
  end
  array
end
heapify_up(array, child_idx, len = array.length, &prc) click to toggle source
# File lib/simms_structures/heap.rb, line 69
def self.heapify_up(array, child_idx, len = array.length, &prc)
  return if child_idx == 0
  prc ||= Proc.new { |a, b| a <=> b }

  parent_idx = BinaryMinHeap.parent_index(child_idx)
  if prc.call(array[parent_idx], array[child_idx]) > -1
    array[parent_idx], array[child_idx] = array[child_idx], array[parent_idx]
    BinaryMinHeap.heapify_up(array, parent_idx, len, &prc)
  end
  array
end
new(&prc) click to toggle source
# File lib/simms_structures/heap.rb, line 2
def initialize(&prc)
  @prc = prc
  @store = Array.new
end
parent_index(child_idx) click to toggle source
# File lib/simms_structures/heap.rb, line 41
def self.parent_index(child_idx)
  raise 'root has no parent' if child_idx == 0
  ( child_idx - 1 ) / 2
end

Public Instance Methods

count() click to toggle source
# File lib/simms_structures/heap.rb, line 7
def count
  @store.length
end
extract() click to toggle source
# File lib/simms_structures/heap.rb, line 15
def extract
  last = @store.length - 1
  @store[0], @store[last] = @store[last], @store[0]
  output = @store.pop
  BinaryMinHeap.heapify_down(@store, 0)
  output
end
insert(val) click to toggle source
# File lib/simms_structures/heap.rb, line 23
def insert(val)
  @store.push(val)
  BinaryMinHeap.heapify_up(@store, @store.length - 1)
end
peek() click to toggle source
# File lib/simms_structures/heap.rb, line 11
def peek
  @store.last
end