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