Class: CollectionUtils::HeapUtils::MaxHeap

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

Instance Attribute Summary

Attributes inherited from CollectionUtils::Heap

#level, #root, #size

Instance Method Summary collapse

Methods inherited from CollectionUtils::Heap

#bfs, #dfs, #inorder, #is_empty?, #postorder, #preorder

Constructor Details

#initialize(array = []) ⇒ MaxHeap

Returns a new instance of MaxHeap.



68
69
70
71
72
73
74
75
76
 
# File 'lib/collection_utils/heap_utils/max_heap.rb', line 68

def initialize(array = [])
  @size = 0
  @root = nil
  @incomplete_set = CollectionUtils::Set.new()
  @leaf_set = CollectionUtils::Set.new()
  array.each_with_index do |element, index|
    insert(element)
  end
end

Instance Method Details

#extract_max ⇒ Object Also known as: delete

This will insert the value in max heap. This takes O(logn) operations as adding the element will trigger the correction of the tree

> @heap = CollectionUtils::HeapUtils::MaxHeap.new()

> # Max Heap would look like this

> # 5

> # / \

> # 4 3

> # /

> # 2

> value = @heap.extract_max

> # 4

> # / \

> # 2 3

> #

> # value = 5

Examples:

Max heap remove maximum value and return it

Returns:

  • maximum value



178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
 
# File 'lib/collection_utils/heap_utils/max_heap.rb', line 178

def extract_max
  return if is_empty?
  if size == 1
    @size = 0
    value = @root.val
    @root = nil
    return value
  end
  maximum = @root.val
  @size -= 1
  node = @leaf_set.get
  replaced_value = node.val
  @leaf_set.delete(node)
  @incomplete_set.delete(node)
  parent = node.parent
  parent.left == node ? parent.left = nil : parent.right = nil
  @leaf_set.delete(parent)
  @incomplete_set.delete(parent)
  node = nil
  @incomplete_set.insert(parent) if parent.is_incomplete?
  @leaf_set.insert(parent) if parent.is_leaf?

  @leaf_set.delete(@root)
  @incomplete_set.delete(@root)
  @root.val = replaced_value
  @incomplete_set.insert(@root) if @root.is_incomplete?
  @leaf_set.insert(@root) if @root.is_leaf?
  heapify(@root)
  return maximum
end

#get_max ⇒ Object

This will insert the value in max heap. This takes O(1) operations

> @heap = CollectionUtils::HeapUtils::MaxHeap.new()

> # Max Heap would look like this

> # 5

> # / \

> # 4 3

> # /

> # 2

> value = @heap.get_max

> # 5

> # / \

> # 4 3

> # /

> # 2

> # value = 5

Examples:

Max heap remove maximum value and return it

Returns:

  • maximum value



156
157
158
159
 
# File 'lib/collection_utils/heap_utils/max_heap.rb', line 156

def get_max
  return if is_empty?
  return @root.val
end

#insert(element) ⇒ Object

Removes the maximum value element from heap and corrects the whole heap again. This is done in O(logn) operations as correction of tree takes logn time

> @heap = CollectionUtils::HeapUtils::MaxHeap.new()

> # Min Heap would look like this

> # 5

> # / \

> # 4 3

> # /

> # 2

> @heap.insert(6)

> # 6

> # / \

> # 5 3

> # / \

> # 2 4

Examples:

Max heap should return maximum value

Returns:

  • maximum value



96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
 
# File 'lib/collection_utils/heap_utils/max_heap.rb', line 96

def insert(element)
  node = Node.new(element)
  @size += 1
  if @root.nil?
    @root = node
    @root.level = 1
    @level = 1
    @leaf_set.insert(node)
    return
  end
  unless @incomplete_set.is_empty?
    parent_node = @incomplete_set.get
    @incomplete_set.delete(parent_node)
    if parent_node.left.nil?
      node.parent = parent_node
      node.level = parent_node.level + 1
      parent_node.left = node
      @level = node.level if node.level > @level
      bubble_up(node)
      return
    end
    if parent_node.right.nil?
      node.parent = parent_node
      node.level = parent_node.level + 1
      parent_node.right = node
      @level = node.level if node.level > @level
      bubble_up(node)
      return
    end
  end

  unless @leaf_set.is_empty?
    parent_node = @leaf_set.get
    @leaf_set.delete(parent_node)
    node.parent = parent_node
    node.level = parent_node.level + 1
    parent_node.left = node
    @level = node.level if node.level > @level
    bubble_up(node)
    return
  end
end