class RubyCollections::MinHeap

Attributes

heap[R]

Public Class Methods

new(arr = []) click to toggle source
# File lib/ruby_collections/min_heap.rb, line 4
def initialize(arr = [])
  @heap = arr.unshift(nil)
  (@heap.length/2).downto(1) do |i|
    heapify(i)
  end
end

Public Instance Methods

extract_min() click to toggle source
# File lib/ruby_collections/min_heap.rb, line 11
def extract_min
  min, length = heap[1], heap.length
  heap[1] = nil
  swap(1, length-1)
  heapify(1)
  heap.pop
  return min
end
insert(val) click to toggle source
# File lib/ruby_collections/min_heap.rb, line 28
def insert(val)
  heap[heap.length], parent, current = val, parent(heap.length), heap.length
  until heap[parent] <= val
    swap(current, parent)
    current = parent
    parent = parent(parent)
  end
  val
end
min() click to toggle source
# File lib/ruby_collections/min_heap.rb, line 20
def min
  heap[1]
end
size() click to toggle source
# File lib/ruby_collections/min_heap.rb, line 24
def size
  @heap.length-1
end

Private Instance Methods

heapify(i) click to toggle source
# File lib/ruby_collections/min_heap.rb, line 52
def heapify(i)
  left, right,smallest = left(i), right(i), i
  smallest = left if heap[left] and heap[left] < heap[smallest]
  smallest = right if heap[right] and heap[right] < heap[smallest]
  unless smallest == i
    swap(smallest, i)
    heapify(smallest)
  end
end
left(i) click to toggle source
# File lib/ruby_collections/min_heap.rb, line 44
def left(i)
  2*i
end
parent(i) click to toggle source
# File lib/ruby_collections/min_heap.rb, line 40
def parent(i)
  i == 1 ? 1 : i/2
end
right(i) click to toggle source
# File lib/ruby_collections/min_heap.rb, line 48
def right(i)
  2*i+1
end
swap(i,j) click to toggle source
# File lib/ruby_collections/min_heap.rb, line 62
def swap(i,j)
  temp  = heap[j]
  heap[j] = heap[i]
  heap[i] = temp
end