Class: Heap::BinaryHeap::MinHeap

Inherits:
Object
  • Object
show all
Defined in:
lib/Heap/binary_heap/binary_heap_min.rb

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(elements = []) ⇒ MinHeap

Returns a new instance of MinHeap.



6
7
8
9
 
# File 'lib/Heap/binary_heap/binary_heap_min.rb', line 6

def initialize(elements = [])
  @elements = []
  add(elements.pop) until elements.empty?
end

Instance Attribute Details

#elements ⇒ Object (readonly)

Returns the value of attribute elements.



4
5
6
 
# File 'lib/Heap/binary_heap/binary_heap_min.rb', line 4

def elements
  @elements
end

Instance Method Details

#add(element) ⇒ Object 



11
12
13
14
15
16
17
18
19
20
21
22
23
 
# File 'lib/Heap/binary_heap/binary_heap_min.rb', line 11

def add(element)
  if element.is_a? Array
    element.each do |el|
      @elements.push el
      swim_up(count)
    end
  elsif defined? element.elements
    add element.elements
  else
    @elements.push element
    swim_up(count)
  end
end

#count ⇒ Object 



25
26
27
 
# File 'lib/Heap/binary_heap/binary_heap_min.rb', line 25

def count
  @elements.length
end

#extract_min ⇒ Object 



29
30
31
 
# File 'lib/Heap/binary_heap/binary_heap_min.rb', line 29

def extract_min
  @elements[0]
end

#extract_min! ⇒ Object 



33
34
35
36
37
38
 
# File 'lib/Heap/binary_heap/binary_heap_min.rb', line 33

def extract_min!
  swap(1, count)
  el = @elements.pop
  swim_down(1)
  el
end

#sort ⇒ Object 



40
41
42
43
44
45
46
 
# File 'lib/Heap/binary_heap/binary_heap_min.rb', line 40

def sort
  el_temp = @elements.clone
  result = []
  result.push extract_min! while count > 0
  @elements = el_temp
  result
end