class DataStructures101::Heap
Heap
implementation @author Rene Hernandez @since 0.3
Attributes
min_heap[R]
Public Class Methods
new(*args, min_heap: false)
click to toggle source
# File lib/data_structures_101/heap.rb, line 11 def initialize(*args, min_heap: false) @data = args @min_heap = min_heap @heap_check = ->(i, j) { return @data[i] >= @data[j] } if @min_heap @heap_check = ->(i, j) { return @data[i] <= @data[j] } end build_heap end
Public Instance Methods
[](i)
click to toggle source
# File lib/data_structures_101/heap.rb, line 27 def [](i) @data[i] end
left(i)
click to toggle source
# File lib/data_structures_101/heap.rb, line 52 def left(i) 2 * i + 1 end
merge(heap)
click to toggle source
# File lib/data_structures_101/heap.rb, line 46 def merge(heap) new_array = @data + heap.instance_variable_get(:@data) Heap.new(new_array, min_heap: self.min_heap) end
parent(i)
click to toggle source
# File lib/data_structures_101/heap.rb, line 60 def parent(i) (i - 1) / 2 end
pop()
click to toggle source
# File lib/data_structures_101/heap.rb, line 39 def pop result = @data.first @data[0] = @data.pop heapify(0) result end
push(*values)
click to toggle source
# File lib/data_structures_101/heap.rb, line 31 def push(*values) values.each do |val| @data.push(val) upheap(@data.size - 1) end self end
right(i)
click to toggle source
# File lib/data_structures_101/heap.rb, line 56 def right(i) 2 * (i + 1) end
size()
click to toggle source
# File lib/data_structures_101/heap.rb, line 23 def size @data.size end
Private Instance Methods
build_heap()
click to toggle source
# File lib/data_structures_101/heap.rb, line 66 def build_heap start = @data.size / 2 start.downto(0) { |i| heapify(i) } end
heapify(i)
click to toggle source
# File lib/data_structures_101/heap.rb, line 72 def heapify(i) l = left(i) r = right(i) head = i head = l if l < @data.size && @heap_check.call(l, head) head = r if r < @data.size && @heap_check.call(r, head) if head != i @data[i], @data[head] = @data[head], @data[i] heapify(head) end end
upheap(idx)
click to toggle source
# File lib/data_structures_101/heap.rb, line 86 def upheap(idx) p = parent(idx) if @heap_check.call(idx, p) @data[idx], @data[p] = @data[p], @data[idx] upheap(p) end end