Class: DSA::MinHeap

Inherits:
Object
  • Object
show all
Defined in:
lib/dsa-ruby/heap.rb

Instance Method Summary collapse

Constructor Details

#initialize(elements = []) ⇒ MinHeap

Returns a new instance of MinHeap.



3
4
5
6
 
# File 'lib/dsa-ruby/heap.rb', line 3

def initialize(elements = [])
  @elements = []
  elements.each { |e| push(e) }
end

Instance Method Details

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


32
33
34
 
# File 'lib/dsa-ruby/heap.rb', line 32

def empty?
  @elements.empty?
end

#peek ⇒ Object

Raises:

  • (IndexError) 


23
24
25
26
 
# File 'lib/dsa-ruby/heap.rb', line 23

def peek
  raise IndexError, "heap is empty" if empty?
  @elements[0]
end

#pop ⇒ Object

Raises:

  • (IndexError) 


14
15
16
17
18
19
20
21
 
# File 'lib/dsa-ruby/heap.rb', line 14

def pop
  raise IndexError, "heap is empty" if empty?

  swap(0, @elements.size - 1)
  min = @elements.pop
  sift_down(0)
  min
end

#push(val) ⇒ Object 



8
9
10
11
12
 
# File 'lib/dsa-ruby/heap.rb', line 8

def push(val)
  @elements << val
  sift_up(@elements.size - 1)
  self
end

#size ⇒ Object 



28
29
30
 
# File 'lib/dsa-ruby/heap.rb', line 28

def size
  @elements.size
end

#to_a ⇒ Object 



36
37
38
 
# File 'lib/dsa-ruby/heap.rb', line 36

def to_a
  @elements.dup
end