Class: CollectionUtils::HeapUtils::MinHeap

Inherits:
CollectionUtils::Heap show all
Defined in:
lib/collection_utils/heap_utils/min_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 = []) ⇒ MinHeap

Returns a new instance of MinHeap.



68
69
70
71
72
73
74
75
76
 
# File 'lib/collection_utils/heap_utils/min_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_min ⇒ Object Also known as: delete

Removes the minimum 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::MinHeap.new()

> # Min Heap would look like this

> # 2

> # / \

> # 5 3

> # /

> # 4

> value = @heap.extract_min

> # 3

> # / \

> # 5 4

> # value = 2

Examples:

Min heap should return minimum value

Returns:

  • minimum 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/min_heap.rb', line 178

def extract_min
  return if is_empty?
  if size == 1
    @size = 0
    value = @root.val
    @root = nil
    return value
  end
  minimum = @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 minimum
end

#get_min ⇒ Object

Returns the minimum value element from heap and This is done in O(1) operations.

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

> # Min Heap would look like this

> # 2

> # / \

> # 5 3

> # /

> # 4

> value = @heap.get_min

> # 2

> # / \

> # 5 3

> # /

> # 4

> # value = 2

Examples:

Min heap should return minimum value

Returns:

  • minimum value



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

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

#insert(element) ⇒ Object

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

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

> # Min Heap would look like this

> # 2

> # / \

> # 5 3

> # /

> # 4

> @heap.insert(1)

> # 1

> # / \

> # 2 3

> # / \

> # 4 5

Examples:

Min heap should add another element

Parameters:

  • element —

    which needs to be added into the min heap



95
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
 
# File 'lib/collection_utils/heap_utils/min_heap.rb', line 95

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