Sha256: 7c740803fb18721d4dab47b5af863f0e511233bcfe088b51380e2e1404f6d5aa
Contents?: true
Size: 1.28 KB
Versions: 7
Compression:
Stored size: 1.28 KB
Contents
module RubyCollections
class MinHeap
attr_reader :heap
def initialize(arr = [])
@heap = arr.unshift(nil)
(@heap.length/2).downto(1) do |i|
heapify(i)
end
end
def extract_min
min, length = heap[1], heap.length
heap[1] = nil
swap(1, length-1)
heapify(1)
heap.pop
return min
end
def min
heap[1]
end
def size
@heap.length-1
end
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
private
def parent(i)
i == 1 ? 1 : i/2
end
def left(i)
2*i
end
def right(i)
2*i+1
end
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
def swap(i,j)
temp = heap[j]
heap[j] = heap[i]
heap[i] = temp
end
end
end
Version data entries
7 entries across 7 versions & 1 rubygems