Class: CollectionUtils::HeapUtils::Heap

Inherits:
Object
  • Object
show all
Defined in:
lib/collection_utils/heap_utils/heap.rb

Direct Known Subclasses

MaxHeap, MinHeap

Instance Method Summary collapse

Constructor Details

#initialize(array = []) ⇒ Heap

Constructors



9
10
11
 
# File 'lib/collection_utils/heap_utils/heap.rb', line 9

def initialize(array = [])
  @heap = array
end

Instance Method Details

#assign_left(parent = 0, node) ⇒ Object 



39
40
41
42
 
# File 'lib/collection_utils/heap_utils/heap.rb', line 39

def assign_left(parent =0, node)
  left = (2*parent + 1)
  @heap[left] = node
end

#assign_right(parent = 0, node) ⇒ Object 



44
45
46
47
 
# File 'lib/collection_utils/heap_utils/heap.rb', line 44

def assign_right(parent =0, node)
  right = (2*parent + 2)
  @heap[right] = node
end

#bfs ⇒ Object 



62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
 
# File 'lib/collection_utils/heap_utils/heap.rb', line 62

def bfs
  queue = CollectionUtils::Queue.new
  queue.enqueue({element: @heap.first, index: 0})
  while true do
    node = queue.dequeue
    break if node.nil?
    left = left_child(node[:index])
    right = right_child(node[:index])
    yield(node[:element]) if block_given?
    queue.enqueue({element: left.first, index: left.last}) if !left.first.nil?
    queue.enqueue({element: right.first, index: right.last}) if !right.first.nil?
    break if left.first.nil? && right.first
  end

end

#dfs ⇒ Object 



78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
 
# File 'lib/collection_utils/heap_utils/heap.rb', line 78

def dfs
  stack = CollectionUtils::Stack.new
  stack.push({element: @heap.first, index: 0})
  while true do
    node = stack.pop
    break if node.nil?
    left = left_child(node[:index])
    right = right_child(node[:index])
    yield(node[:element]) if block_given?
    stack.push({element: left.first, index: left.last}) if !left.first.nil?
    stack.push({element: right.first, index: right.last}) if !right.first.nil?
    break if left.first.nil? && right.first
  end

end

#is_empty? ⇒ Boolean

Returns:

  • (Boolean) 


58
59
60
 
# File 'lib/collection_utils/heap_utils/heap.rb', line 58

def is_empty?
  return size == 0
end

#left_child(parent = 0) ⇒ Object 



27
28
29
30
31
 
# File 'lib/collection_utils/heap_utils/heap.rb', line 27

def left_child(parent = 0)
  left = (2*parent + 1)
  return nil, nil if @heap[left].nil?
  return @heap[left], left
end

#parent(child = 0) ⇒ Object 



49
50
51
52
 
# File 'lib/collection_utils/heap_utils/heap.rb', line 49

def parent(child = 0)
  par = child/2
  return @heap[par], par
end

#pop ⇒ Object 



22
23
24
25
 
# File 'lib/collection_utils/heap_utils/heap.rb', line 22

def pop
  element = @heap.pop
  return element
end

#push(element) ⇒ Object 



18
19
20
 
# File 'lib/collection_utils/heap_utils/heap.rb', line 18

def push(element)
  @heap << element
end

#right_child(parent = 0) ⇒ Object 



33
34
35
36
37
 
# File 'lib/collection_utils/heap_utils/heap.rb', line 33

def right_child(parent = 0)
  right = (2*parent + 2)
  return nil, nil if @heap[right].nil?
  return @heap[right], right
end

#root ⇒ Object

Public methods



14
15
16
 
# File 'lib/collection_utils/heap_utils/heap.rb', line 14

def root
  return @heap.first
end

#size ⇒ Object 



54
55
56
 
# File 'lib/collection_utils/heap_utils/heap.rb', line 54

def size
  return @heap.size
end