class BinaryMinHeap

MinHeap helper class for Heap Sort

Attributes

prc[RW]
store[RW]

Public Class Methods

child_indices(len, parent_index) click to toggle source
# File lib/algorithm_selector.rb, line 626
def self.child_indices(len, parent_index)
  [2 * parent_index + 1, 2 * parent_index + 2].select { |idx| idx < len }
end
heapify_down(array, parent_idx, len = array.length, &prc) click to toggle source
# File lib/algorithm_selector.rb, line 635
def self.heapify_down(array, parent_idx, len = array.length, &prc)
  prc ||= Proc.new { |el1, el2| el1 <=> el2 }

  left_child, right_child = child_indices(len, parent_idx)

  parent = array[parent_idx]

  children = []
  children.push(array[left_child]) if left_child
  children.push(array[right_child]) if right_child

  if children.all? { |child| prc.call(parent, child) <= 0 }
    return array
  end

  swap_idx = nil
  if children.length == 1
    swap_idx = left_child
  else
    swap_idx =
      prc.call(children[0], children[1]) == -1 ? left_child : right_child
  end

  array[parent_idx], array[swap_idx] = array[swap_idx], parent
  heapify_down(array, swap_idx, len, &prc)
end
heapify_up(array, child_idx, len = array.length, &prc) click to toggle source
# File lib/algorithm_selector.rb, line 662
def self.heapify_up(array, child_idx, len = array.length, &prc)
  prc ||= Proc.new { |el1, el2| el1 <=> el2 }
  return array if child_idx == 0

  parent_idx = parent_index(child_idx)
  child, parent = array[child_idx], array[parent_idx]
  if prc.call(child, parent) >= 0
    return array
  else
    array[child_idx], array[parent_idx] = parent, child
    heapify_up(array, parent_idx, len, &prc)
  end
end
new(&prc) click to toggle source
# File lib/algorithm_selector.rb, line 592
def initialize(&prc)
  @store = []
  @prc = prc || Proc.new { |el1, el2| el1 <=> el2 }
end
parent_index(child_index) click to toggle source
# File lib/algorithm_selector.rb, line 630
def self.parent_index(child_index)
  raise "root has no parent" if child_index == 0
  (child_index - 1) / 2
end

Public Instance Methods

count() click to toggle source
# File lib/algorithm_selector.rb, line 597
def count
  @store.length
end
extract() click to toggle source
# File lib/algorithm_selector.rb, line 601
def extract
  raise "no element to extract" if count == 0
  val = @store[0]
  @store.pop if count == 1
  if count > 1
    @store[0] = @store.pop
    self.class.heapify_down(@store, 0, &@prc)
  end
  val
end
peek() click to toggle source
# File lib/algorithm_selector.rb, line 612
def peek
  raise "no element to peek" if count == 0
  @store[0]
end
push(val) click to toggle source
# File lib/algorithm_selector.rb, line 617
def push(val)
  @store.push(val)
  self.class.heapify_up(@store, count - 1, &@prc)
end