class Heap

Attributes

store[R]

Public Class Methods

from_array(array) click to toggle source
# File lib/data_structures/heap.rb, line 2
def self.from_array(array)
  heap = Heap.new
  heap.instance_variable_set(:@store, array)

  heap.send(:store).length.downto(0).each do |idx|
    children_indices = heap.send(:children_indices, idx)
    heap.send(:heapify_down, idx, children_indices) unless children_indices.empty?
  end

  heap
end
new() click to toggle source
# File lib/data_structures/heap.rb, line 14
def initialize
  @store = []
end

Public Instance Methods

empty?() click to toggle source
# File lib/data_structures/heap.rb, line 36
def empty?
  @store.empty?
end
extract() click to toggle source
# File lib/data_structures/heap.rb, line 66
def extract
  return nil if @store.empty?
  return @store.shift if @store.length <= 2

  @store[0], @store[-1] = @store[-1], @store[0]
  head = @store.pop

  el_idx = 0
  children_indices = children_indices(el_idx)

  heapify_down(el_idx, children_indices) unless children_indices.empty?

  head
end
find(el) click to toggle source
# File lib/data_structures/heap.rb, line 81
def find(el)
  return nil if @store.empty? || el < @store.first
  @store.each { |store_el| return store_el if store_el == el }
  nil
end
include?(el) click to toggle source
# File lib/data_structures/heap.rb, line 87
def include?(el)
  @store.include?(el)
end
insert(el) click to toggle source
# File lib/data_structures/heap.rb, line 49
def insert(el)
  @store << el

  el_idx = @store.length - 1
  parent_idx = parent_idx(el_idx)

  heapify_up(el_idx, parent_idx)

  el
end
insert_mutliple(arr) click to toggle source
# File lib/data_structures/heap.rb, line 60
def insert_mutliple(arr)
  raise ArgumentError.new("Can only insert multiple elements via an Array. You passed a #{arr.class}.") unless arr.is_a?(Array)
  array = self.send(:store) + arr
  self.class.from_array(array)
end
inspect() click to toggle source
# File lib/data_structures/heap.rb, line 32
def inspect
  "Heap: head=#{self.peek || 'nil'}, length=#{self.length}"
end
length() click to toggle source
# File lib/data_structures/heap.rb, line 40
def length
  @store.length
end
merge(other_heap) click to toggle source
# File lib/data_structures/heap.rb, line 91
def merge(other_heap)
  raise ArgumentError.new("May only merge with a Heap. You passed a #{other_heap.class}.") unless other_heap.is_a?(Heap)
  array = self.send(:store) + other_heap.send(:store)
  self.class.from_array(array)
end
peek() click to toggle source
# File lib/data_structures/heap.rb, line 44
def peek
  return nil if @store.empty?
  @store.first
end
to_a() click to toggle source
# File lib/data_structures/heap.rb, line 18
def to_a
  arr = []
  copy = self.dup
  copy.instance_variable_set(:@store, @store.dup)
  until copy.empty?
    arr << copy.extract
  end
  arr
end
to_s() click to toggle source
# File lib/data_structures/heap.rb, line 28
def to_s
  "Heap: head=#{self.peek || 'nil'}, length=#{self.length}"
end

Private Instance Methods

children_indices(idx) click to toggle source
# File lib/data_structures/heap.rb, line 128
def children_indices(idx)
  idx1 = idx * 2 + 1
  idx2 = idx * 2 + 2
  [idx1, idx2].select { |idx| @store[idx] }
end
heapify_down(el_idx, children_indices) click to toggle source
# File lib/data_structures/heap.rb, line 107
def heapify_down(el_idx, children_indices)
  if children_indices.length == 1
    child_idx = children_indices.first
    if @store[el_idx] > @store[child_idx]
      @store[el_idx], @store[child_idx] = @store[child_idx], @store[el_idx]
    end
    return
  elsif @store[el_idx] > @store[children_indices.first] || @store[el_idx] > @store[children_indices.last]
    child1, child2 = @store[children_indices.first], @store[children_indices.last]
    lowest_child_idx = child1 <= child2 ? children_indices.first : children_indices.last
    @store[el_idx], @store[lowest_child_idx] = @store[lowest_child_idx], @store[el_idx]

    children_indices = children_indices(lowest_child_idx)
    heapify_down(lowest_child_idx, children_indices) unless children_indices.empty?
  end
end
heapify_up(el_idx, parent_idx) click to toggle source
# File lib/data_structures/heap.rb, line 99
def heapify_up(el_idx, parent_idx)
  until el_idx == 0 || @store[el_idx] >= @store[parent_idx]
    @store[el_idx], @store[parent_idx] = @store[parent_idx], @store[el_idx]
    el_idx = parent_idx
    parent_idx = parent_idx(el_idx)
  end
end
parent_idx(idx) click to toggle source
# File lib/data_structures/heap.rb, line 124
def parent_idx(idx)
  (idx - 1) / 2
end