class Heap::MultipleHeap::MinHeap

Multiple Heap with min root

Public Instance Methods

extract_min() click to toggle source
# File lib/Heap/multiple_heap/multiple_heap_min.rb, line 5
def extract_min
  extract_root
end
extract_min!() click to toggle source
# File lib/Heap/multiple_heap/multiple_heap_min.rb, line 9
def extract_min!
  extract_root!
end

Private Instance Methods

swim_down(index) click to toggle source
# File lib/Heap/multiple_heap/multiple_heap_min.rb, line 23
def swim_down(index)
  children = get_children index
  return if children.nil? || children.empty?
  min_child = children.min

  return if @elements[index - 1] <= min_child[0]
  swap index, min_child[1]
  swim_down min_child[1]
end
swim_up(index) click to toggle source
# File lib/Heap/multiple_heap/multiple_heap_min.rb, line 15
def swim_up(index)
  return if index == 1
  parent_index = ((index.to_f - 1) / @d).ceil
  return if @elements[parent_index - 1] <= @elements[index - 1]
  swap(parent_index, index)
  swim_up parent_index
end