Class: RubyCollections::MinHeap

Inherits:
Object
  • Object
show all
Defined in:
lib/ruby_collections/min_heap.rb

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(arr = []) ⇒ MinHeap

Returns a new instance of MinHeap.



4
5
6
7
8
9
 
# File 'lib/ruby_collections/min_heap.rb', line 4

def initialize(arr = [])
  @heap = arr.unshift(nil)
  (@heap.length/2).downto(1) do |i|
    heapify(i)
  end
end

Instance Attribute Details

#heap ⇒ Object (readonly)

Returns the value of attribute heap.



3
4
5
 
# File 'lib/ruby_collections/min_heap.rb', line 3

def heap
  @heap
end

Instance Method Details

#extract_min ⇒ Object 



11
12
13
14
15
16
17
18
 
# File 'lib/ruby_collections/min_heap.rb', line 11

def extract_min
  min, length = heap[1], heap.length
  heap[1] = nil
  swap(1, length-1)
  heapify(1)
  heap.pop
  return min
end

#insert(val) ⇒ Object 



28
29
30
31
32
33
34
35
36
 
# File 'lib/ruby_collections/min_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
  val
end

#min ⇒ Object 



20
21
22
 
# File 'lib/ruby_collections/min_heap.rb', line 20

def min
  heap[1]
end

#size ⇒ Object 



24
25
26
 
# File 'lib/ruby_collections/min_heap.rb', line 24

def size
  @heap.length-1
end