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