class RubyCollections::MaxHeap

Attributes

heap[R]

Public Class Methods

new(arr = []) click to toggle source
# File lib/ruby_collections/max_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_max() click to toggle source
# File lib/ruby_collections/max_heap.rb, line 11
def extract_max
  max, length = heap[1], heap.length
  heap[1] = nil
  swap(1, length-1)
  heapify(1)
  heap.pop
  return max
end
insert(val) click to toggle source
# File lib/ruby_collections/max_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
end
max() click to toggle source
# File lib/ruby_collections/max_heap.rb, line 20
def max
  heap[1]
end
size() click to toggle source
# File lib/ruby_collections/max_heap.rb, line 24
def size
  @heap.length-1
end

Private Instance Methods

heapify(i) click to toggle source
# File lib/ruby_collections/max_heap.rb, line 51
def heapify(i)
  left, right,maximum = left(i), right(i), i
  maximum = left if heap[left] and heap[left] > heap[maximum]
  maximum = right if heap[right] and heap[right] > heap[maximum]
  unless maximum == i
    swap(maximum, i)
    heapify(maximum)
  end
end
left(i) click to toggle source
# File lib/ruby_collections/max_heap.rb, line 43
def left(i)
  2*i
end
parent(i) click to toggle source
# File lib/ruby_collections/max_heap.rb, line 39
def parent(i)
  i == 1 ? 1 : i/2
end
right(i) click to toggle source
# File lib/ruby_collections/max_heap.rb, line 47
def right(i)
  2*i+1
end
swap(i,j) click to toggle source
# File lib/ruby_collections/max_heap.rb, line 61
def swap(i,j)
  temp  = heap[j]
  heap[j] = heap[i]
  heap[i] = temp
end