class Heap::BinaryHeap::MinHeap

Binary Heap with min root

Public Instance Methods

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

Private Instance Methods

swim_down(index) click to toggle source
# File lib/Heap/binary_heap/binary_heap_min.rb, line 23
def swim_down(index)
  children = get_children(index)
  return if children.empty?
  max_child = children.min
  return if @elements[index - 1] <= max_child[0]
  swap index, max_child[1]
  swim_down max_child[1]
end
swim_up(index) click to toggle source
# File lib/Heap/binary_heap/binary_heap_min.rb, line 15
def swim_up(index)
  return if index == 1
  parent_index = index / 2
  return if @elements[parent_index - 1] <= @elements[index - 1]
  swap(parent_index, index)
  swim_up parent_index
end