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