Class: CollectionUtils::Heap

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

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(array = []) ⇒ Heap

Constructors



85
86
87
88
89
90
91
92
93
 
# File 'lib/collection_utils/heap.rb', line 85

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

Instance Attribute Details

#level ⇒ Integer

Returns the level of the tree. This is returned in O(1) operations as we are storing the level of the tree which is otherwise a costly operation

Returns:

  • (Integer) —

    height or level of the heap or tree



222
223
224
 
# File 'lib/collection_utils/heap.rb', line 222

def level
  @level
end

#root ⇒ Object

Returns the root of the tree

> @heap = CollectionUtils::Heap.new()

> # 5

> # / \

> # 2 6

> # / \

> # 4 3

> @heap.root == 5

Examples:

Root of heap [5,2,6,4,3]

Returns:

  • element which is present at the root of the heap or tree



198
199
200
 
# File 'lib/collection_utils/heap.rb', line 198

def root
  @root
end

#size ⇒ Integer

Returns the number of elements in a tree or heap. This is returned in O(1) operations as we are storing the size of the tree which is otherwise O(n) operations.

Returns:

  • (Integer) —

    size of heap



206
207
208
 
# File 'lib/collection_utils/heap.rb', line 206

def size
  @size
end

Instance Method Details

#bfs {|element| ... } ⇒ Object

bfs stands for breadth first search.

Examples:

Create Heap and in bfs manner assign it to array

arr = [1,2,3,4,5]
heap = CollectionUtils::Heap.new(arr)
x = []
heap.bfs do |element|
  x << element
end
#x = [1,2,3,4,5]

Yields:

  • (element) —

    this will take the element returned in bfs manner and execute the passed block.



237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
 
# File 'lib/collection_utils/heap.rb', line 237

def bfs
  queue = CollectionUtils::Queue.new
  queue.enqueue(@root)
  while true do
    node = queue.dequeue
    next if node.nil?
    left = node.left
    right = node.right
    yield(node.val) if block_given?
    queue.enqueue(left) unless left.nil?
    queue.enqueue(right) unless right.nil?
    break if queue.is_empty?
  end

end

#delete ⇒ Object

Removes a random element from the leaf set and deletes it. This is done in O(1) operations.

> @heap = CollectionUtils::Heap.new()

> # 5

> # / \

> # 2 6

> # / \

> # 4 3

> @heap.delete == 4 or 3 or 6

Examples:

delete from heap [5,2,6,4,3]

Returns:

  • removed element



168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
 
# File 'lib/collection_utils/heap.rb', line 168

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

#dfs {|element| ... } ⇒ Object

dfs stands for depth first search.

Examples:

Create Heap and in dfs manner assign it to array

arr = [1,2,3,4,5]
heap = CollectionUtils::Heap.new(arr)
x = []
heap.dfs do |element|
  x << element
end
#x = [1,3,5,4,2]

Yields:

  • (element) —

    this will take the element returned in dfs manner and execute the passed block.



263
264
265
266
267
268
269
270
271
272
273
274
275
276
 
# File 'lib/collection_utils/heap.rb', line 263

def dfs
  stack = CollectionUtils::Stack.new
  stack.push(@root)
  while true do
    node = stack.pop
    next if node.nil?
    left = node.left
    right =node.right
    yield(node.val) if block_given?
    stack.push(left) unless left.nil?
    stack.push(right) unless right.nil?
    break if stack.is_empty?
  end
end

#inorder ⇒ Array

In-Order Traversal of Tree

> @heap = CollectionUtils::Heap.new()

> # 5

> # / \

> # 2 6

> # / \

> # 4 3

> arr = @heap.inorder #arr = [4,2,3,5,6]

Examples:

Inorder Traversal for heap [5,2,6,4,3]

Returns:

  • (Array) —

    elements of heap in in-ordered manner



323
324
325
326
327
 
# File 'lib/collection_utils/heap.rb', line 323

def inorder
  arr = []
  in_order(@root, arr)
  return arr
end

#insert(element) ⇒ Object

Adds an element to the heap. This is done in O(1) operations and preference is given to incomplete nodes as compared to leaf nodes

> @heap = CollectionUtils::Heap.new()

> # 5

> # / \

> # 2 6

> # / \

> # 4 3

> @heap.insert(7)

> # 5

> # / \

> # 2 6

> # / \ /

> # 4 3 7

Parameters:

  • element —

    object that needs to be added to heap



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
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
 
# File 'lib/collection_utils/heap.rb', line 110

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
      @incomplete_set.insert(parent_node) if parent_node.right.nil?
      @leaf_set.insert(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
      @incomplete_set.insert(parent_node) if parent_node.left.nil?
      @leaf_set.insert(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
    @incomplete_set.insert(parent_node)
    @leaf_set.insert(node)
    return
  end

end

#is_empty? ⇒ Boolean

Returns whether the heap or tree is empty. This is just a syntax_sugar for size == 0

Returns:

  • (Boolean) —

    heap’s emptiness



213
214
215
 
# File 'lib/collection_utils/heap.rb', line 213

def is_empty?
 size == 0
end

#postorder ⇒ Array

Post-Order Traversal of Tree

> @heap = CollectionUtils::Heap.new()

> # 5

> # / \

> # 2 6

> # / \

> # 4 3

> arr = @heap.postorder #arr = [4,3,2,6,5]

Examples:

Postorder Traversal for heap [5,2,6,4,3]

Returns:

  • (Array) —

    elements of heap in post-ordered manner



306
307
308
309
310
 
# File 'lib/collection_utils/heap.rb', line 306

def postorder
  arr = []
  post_order(@root, arr)
  return arr
end

#preorder ⇒ Array

Pre-Order Traversal of Tree

> @heap = CollectionUtils::Heap.new()

> # 5

> # / \

> # 2 6

> # / \

> # 4 3

> arr = @heap.preorder #arr = [5,2,4,3,6]

Examples:

Preorder Traversal for heap [5,2,6,4,3]

Returns:

  • (Array) —

    elements of heap in pre-ordered manner



289
290
291
292
293
 
# File 'lib/collection_utils/heap.rb', line 289

def preorder
  arr = []
  pre_order(@root, arr)
  return arr
end