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