Class: CollectionUtils::HeapUtils::MaxHeap

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

Instance Method Summary collapse

Methods inherited from Heap

#assign_left, #assign_right, #bfs, #dfs, #is_empty?, #left_child, #parent, #pop, #push, #right_child, #root, #size

Constructor Details

#initialize(array = []) ⇒ MaxHeap

Returns a new instance of MaxHeap.



40
41
42
43
44
45
 
# File 'lib/collection_utils/heap_utils/max_heap.rb', line 40

def initialize(array = [])
  @heap = []
  array.each_with_index do |element, index|
    insert(element)
  end
end

Instance Method Details

#extract_max ⇒ Object 



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

def extract_max
  return if is_empty?
  maximum = max
  if @heap.size > 1
    last_value = @heap.last
    last_value[:index] = 0
    @heap = @heap.slice(0..@heap.size-2)
    @heap[0] = last_value
    heapify(max)
  else
    @heap =[  ]
  end

  return maximum[:element]
end

#get_max ⇒ Object 



59
60
61
62
 
# File 'lib/collection_utils/heap_utils/max_heap.rb', line 59

def get_max
  return if is_empty?
  return max[:element]
end

#insert(value) ⇒ Object 



47
48
49
50
51
52
53
54
55
56
57
 
# File 'lib/collection_utils/heap_utils/max_heap.rb', line 47

def insert(value)
  value = {element: element, index: size}
  @heap << value
  i = @heap.size - 1
  node, index = parent(i)
  while i != 0 && @heap[i][:element] >= node[:element] do
    exchange(@heap[i], node)
    i = index
    node, index = parent(i)
  end
end