Class: Algorithmix::DataStructure::Heap::BinaryHeap

Inherits:
Object
  • Object
show all
Defined in:
lib/algorithmix/data_structure/heap/binary_heap.rb

Instance Method Summary collapse

Constructor Details

#initialize(obj = nil, copy: false, min: false) ⇒ BinaryHeap

Creates a new binary heap.

Raises:

  • ArgumentError, if given object doesn’t respond to #to_a method.

Parameters:

  • (defaults to: nil)

    can be any object, which responds to #to_a method. By default is set to nil.



17
18
19
20
21
 
# File 'lib/algorithmix/data_structure/heap/binary_heap.rb', line 17

def initialize(obj = nil, copy: false, min: false)
  @container = []
  @max = min ? false : true
  obj.nil? ? nil : from_obj(obj, copy)
end

Instance Method Details

#!=(binary_heap) ⇒ true, false

Compares contents of the heap, and a heap given as argument.

Raises:

  • ArgumentError, if given object is not a heap.

Parameters:

Returns:

  • false if heaps are equal, true otherwise



147
148
149
150
 
# File 'lib/algorithmix/data_structure/heap/binary_heap.rb', line 147

def !=(binary_heap)
  raise ArgumentError, "Undefined method BinaryHeap#!= for #{binary_heap}:#{binary_heap.class}" unless binary_heap.is_a?(BinaryHeap)
  @container != binary_heap.to_a
end

#&(binary_heap) ⇒ BinaryHeap

Finds the intersection of contents of the heap, and a heap given as argument.

Raises:

  • ArgumentError, if given object is not a heap

Parameters:

Returns:

  • a new binary heap



245
246
247
248
 
# File 'lib/algorithmix/data_structure/heap/binary_heap.rb', line 245

def &(binary_heap)
  raise ArgumentError, "Undefined method BinaryHeap#& for #{binary_heap}:#{binary_heap.class}" unless binary_heap.is_a?(BinaryHeap)
  BinaryHeap.new(@container & binary_heap.to_a, min: !@max)
end

#+(binary_heap) ⇒ BinaryHeap

Concatenates contents of the heap, and a heap given as argument.

Raises:

  • ArgumentError, if given object is not a heap

Parameters:

Returns:

  • a new binary heap



176
177
178
179
180
 
# File 'lib/algorithmix/data_structure/heap/binary_heap.rb', line 176

def +(binary_heap)
  raise ArgumentError, "Undefined method BinaryHeap#+ for #{binary_heap}:#{binary_heap.class}" unless binary_heap.is_a?(BinaryHeap)

  BinaryHeap.new(@container + binary_heap.to_a, min: !@max)
end

#-(binary_heap) ⇒ BinaryHeap

Finds the difference of contents of the heap, and a heap given as argument.

Raises:

  • ArgumentError, if given object is not a heap

Parameters:

Returns:

  • a new binary heap



271
272
273
274
 
# File 'lib/algorithmix/data_structure/heap/binary_heap.rb', line 271

def -(binary_heap)
  raise ArgumentError, "Undefined method BinaryHeap#- for #{binary_heap}:#{binary_heap.class}" unless binary_heap.is_a?(BinaryHeap)
  BinaryHeap.new(@container - binary_heap.to_a, min: !@max)
end

#<<(value) ⇒ BinaryHeap

Inserts a value in the heap.

Parameters:

Returns:

  • self object



45
46
47
 
# File 'lib/algorithmix/data_structure/heap/binary_heap.rb', line 45

def <<(value)
  insert(value)
end

#<=>(binary_heap) ⇒ Object

Compares contents of the heap, and a heap given as argument.

> 1 if content of the heap is greater than content of the given heap

> 0 if contents are equal

> -1 if content of the given heap is greater than content of the heap

Raises:

  • ArgumentError, if given object is not a heap.

Parameters:

Returns:



166
167
168
169
 
# File 'lib/algorithmix/data_structure/heap/binary_heap.rb', line 166

def <=>(binary_heap)
  raise ArgumentError, "Undefined method BinaryHeap#<=> for #{binary_heap}:#{binary_heap.class}" unless binary_heap.is_a?(BinaryHeap)
  @container <=> binary_heap.to_a
end

#==(binary_heap) ⇒ true, false

Compares contents of the heap, and a heap given as argument.

Raises:

  • ArgumentError, if given object is not a heap.

Parameters:

Returns:

  • true if heaps are equal, false otherwise



131
132
133
134
 
# File 'lib/algorithmix/data_structure/heap/binary_heap.rb', line 131

def ==(binary_heap)
  raise ArgumentError, "Undefined method BinaryHeap#== for #{binary_heap}:#{binary_heap.class}" unless binary_heap.is_a?(BinaryHeap)
  @container == binary_heap.to_a
end

#^(binary_heap) ⇒ BinaryHeap

Finds the symmetric difference of contents of the heap, and a heap given as argument.

Raises:

  • ArgumentError, if given object is not a heap

Parameters:

Returns:

  • a new binary heap



297
298
299
300
301
 
# File 'lib/algorithmix/data_structure/heap/binary_heap.rb', line 297

def ^(binary_heap)
  raise ArgumentError, "Undefined method BinaryHeap#^ for #{binary_heap}:#{binary_heap.class}" unless binary_heap.is_a?(BinaryHeap)
  result = (@container | binary_heap.to_a) - (@container & binary_heap.to_a)
  BinaryHeap.new(result, min: !@max)
end

#apply(&block) ⇒ BinaryHeap

Applies a function to each element of the heap.

Parameters:

Returns:

  • a new binary heap



384
385
386
 
# File 'lib/algorithmix/data_structure/heap/binary_heap.rb', line 384

def apply(&block)
  map(&block)
end

#apply!(&block) ⇒ BinaryHeap

Applies a function to each element of the heap.

Parameters:

Returns:

  • self object



389
390
391
 
# File 'lib/algorithmix/data_structure/heap/binary_heap.rb', line 389

def apply!(&block)
  map!(&block)
end

#assign(obj, copy: false) ⇒ BinaryHeap

Assigns content of an object, to content of the heap.

Raises:

  • ArgumentError, if given object doesn’t respond to #to_a method.

Parameters:

  • can be any object, which responds to #to_a method. By default is set to nil.

Returns:

  • self object



30
31
32
 
# File 'lib/algorithmix/data_structure/heap/binary_heap.rb', line 30

def assign(obj, copy: false)
  from_obj(obj, copy)
end

#clear ⇒ Object

Clears content of the heap.



326
327
328
329
 
# File 'lib/algorithmix/data_structure/heap/binary_heap.rb', line 326

def clear
  @container = []
  self
end

#concat(binary_heap) ⇒ BinaryHeap

Concatenates contents of the heap, and a heap given as argument.

Raises:

  • ArgumentError, if given object is not a heap

Parameters:

Returns:

  • a new binary heap



183
184
185
186
 
# File 'lib/algorithmix/data_structure/heap/binary_heap.rb', line 183

def concat(binary_heap)
  raise ArgumentError, "Undefined method BinaryHeap#concat for #{binary_heap}:#{binary_heap.class}" unless binary_heap.is_a?(BinaryHeap)
  self + binary_heap
end

#concat!(binary_heap) ⇒ BinaryHeap

Concatenates contents of the heap, and a heap given as argument.

Raises:

  • ArgumentError, if given object is not a heap

Parameters:

Returns:

  • self object



199
200
201
202
 
# File 'lib/algorithmix/data_structure/heap/binary_heap.rb', line 199

def concat!(binary_heap)
  raise ArgumentError, "Undefined method BinaryHeap#concat! for #{binary_heap}:#{binary_heap.class}" unless binary_heap.is_a?(BinaryHeap)
  from_obj(@container + binary_heap.to_a, false)
end

#decrease_key(idx: nil, old_value: nil, new_value: nil) ⇒ BinaryHeap

Decreases a value in the heap, if current heap is set to be min heap.

Raises:

  • TypeError, if current heap has type max heap

  • ArgumentError, if idx or old_value are not provided

  • ArgumentError, if new_value is not provided

Returns:

  • self object



114
115
116
117
118
119
120
121
122
123
124
 
# File 'lib/algorithmix/data_structure/heap/binary_heap.rb', line 114

def decrease_key(idx: nil, old_value: nil, new_value: nil)
  raise TypeError, "Undefined method BinaryHeap#decrease_key for MaxBinaryHeap" if @max
  raise ArgumentError, "At least one of both options must be provided." if idx.nil? && old_value.nil?
  raise ArgumentError, ":new_value cannot be nil." if new_value.nil?

  idx = idx.nil? && !old_value.nil? ? @container.index(old_value) : idx
  raise ArgumentError, "Element at position #{idx} doesn't exist." if idx.nil? || @container[idx].nil?
  change_key(idx, new_value)

  self
end

#diff?(binary_heap) ⇒ true, false

Compares contents of the heap, and a heap given as argument.

Raises:

  • ArgumentError, if given object is not a heap.

Parameters:

Returns:

  • false if heaps are equal, true otherwise



153
154
155
156
 
# File 'lib/algorithmix/data_structure/heap/binary_heap.rb', line 153

def diff?(binary_heap)
  raise ArgumentError, "Undefined method BinaryHeap#diff? for #{binary_heap}:#{binary_heap.class}" unless binary_heap.is_a?(BinaryHeap)
  self != binary_heap
end

#difference(binary_heap) ⇒ BinaryHeap

Finds the difference of contents of the heap, and a heap given as argument.

Raises:

  • ArgumentError, if given object is not a heap

Parameters:

Returns:

  • a new binary heap



277
278
279
280
 
# File 'lib/algorithmix/data_structure/heap/binary_heap.rb', line 277

def difference(binary_heap)
  raise ArgumentError, "Undefined method BinaryHeap#difference for #{binary_heap}:#{binary_heap.class}" unless binary_heap.is_a?(BinaryHeap)
  self - binary_heap
end

#difference!(binary_heap) ⇒ BinaryHeap

Finds the difference of contents of the heap, and a heap given as argument.

Raises:

  • ArgumentError, if given object is not a heap

Parameters:

Returns:

  • self object



287
288
289
290
 
# File 'lib/algorithmix/data_structure/heap/binary_heap.rb', line 287

def difference!(binary_heap)
  raise ArgumentError, "Undefined method BinaryHeap#difference! for #{binary_heap}:#{binary_heap.class}" unless binary_heap.is_a?(BinaryHeap)
  from_obj(@container - binary_heap.to_a, false)
end

#empty? ⇒ Boolean

Returns information for current …

Returns:



79
80
81
 
# File 'lib/algorithmix/data_structure/heap/binary_heap.rb', line 79

def empty?
  @container.empty?
end

#eql?(binary_heap) ⇒ true, false

Compares contents of the heap, and a heap given as argument.

Raises:

  • ArgumentError, if given object is not a heap.

Parameters:

Returns:

  • true if heaps are equal, false otherwise



137
138
139
140
 
# File 'lib/algorithmix/data_structure/heap/binary_heap.rb', line 137

def eql?(binary_heap)
  raise ArgumentError, "Undefined method BinaryHeap#eql? for #{binary_heap}:#{binary_heap.class}" unless binary_heap.is_a?(BinaryHeap)
  self == binary_heap
end

#extract ⇒ Object

Removes top element of the heap.

Raises:

  • Algorithmix::EmptyContainerError, if the heap is empty.

Returns:

  • top element of the heap.



53
54
55
56
57
58
59
 
# File 'lib/algorithmix/data_structure/heap/binary_heap.rb', line 53

def extract
  raise EmptyContainerError, "The Binary heap is empty." if @container.empty?
  @container[0], @container[@container.length - 1] = @container[@container.length - 1], @container[0]
  value = @container.pop
  heapify(0)
  value
end

#filter(&block) ⇒ BinaryHeap

Filters elements of the heap by given condition.

Parameters:

Returns:

  • a new binary heap



348
349
350
 
# File 'lib/algorithmix/data_structure/heap/binary_heap.rb', line 348

def filter(&block)
  select(&block)
end

#filter!(&block) ⇒ BinaryHeap

Filters elements of the heap by given condition.

Parameters:

Returns:

  • self object



353
354
355
 
# File 'lib/algorithmix/data_structure/heap/binary_heap.rb', line 353

def filter!(&block)
  select!(&block)
end

#find_all(&block) ⇒ BinaryHeap

Filters elements of the heap by given condition.

Parameters:

Returns:

  • a new binary heap



358
359
360
 
# File 'lib/algorithmix/data_structure/heap/binary_heap.rb', line 358

def find_all(&block)
  select(&block)
end

#find_all!(&block) ⇒ BinaryHeap

Filters elements of the heap by given condition.

Parameters:

Returns:

  • self object



363
364
365
 
# File 'lib/algorithmix/data_structure/heap/binary_heap.rb', line 363

def find_all!(&block)
  select!(&block)
end

#increase_key(idx: nil, old_value: nil, new_value: nil) ⇒ BinaryHeap

Increases a value in the heap, if current heap is set to be max heap.

Raises:

  • TypeError, if current heap has type min heap

  • ArgumentError, if idx or old_value are not provided

  • ArgumentError, if new_value is not provided

Returns:

  • self object



92
93
94
95
96
97
98
99
100
101
102
 
# File 'lib/algorithmix/data_structure/heap/binary_heap.rb', line 92

def increase_key(idx: nil, old_value: nil, new_value: nil)
  raise TypeError, "Undefined method BinaryHeap#increase_key for MinBinaryHeap" if !@max
  raise ArgumentError, "At least one of both options must be provided." if idx.nil? && old_value.nil?
  raise ArgumentError, ":new_value cannot be nil." if new_value.nil?

  idx = idx.nil? && !old_value.nil? ? @container.index(old_value) : idx
  raise ArgumentError, "Element at position #{idx} doesn't exist." if idx.nil? || @container[idx].nil?
  change_key(idx, new_value, increase: true)
  
  self
end

#insert(value) ⇒ BinaryHeap

Inserts a value in the heap.

Parameters:

Returns:

  • self object



38
39
40
41
42
 
# File 'lib/algorithmix/data_structure/heap/binary_heap.rb', line 38

def insert(value)
  @container << value
  sift_up(@container.size - 1)
  self
end

#intersect(binary_heap) ⇒ BinaryHeap

Finds the intersection of contents of the heap, and a heap given as argument.

Raises:

  • ArgumentError, if given object is not a heap

Parameters:

Returns:

  • a new binary heap



251
252
253
254
 
# File 'lib/algorithmix/data_structure/heap/binary_heap.rb', line 251

def intersect(binary_heap)
  raise ArgumentError, "Undefined method BinaryHeap#intersect for #{binary_heap}:#{binary_heap.class}" unless binary_heap.is_a?(BinaryHeap)
  self & binary_heap.to_a
end

#intersect!(binary_heap) ⇒ BinaryHeap

Finds the intersection of contents of the heap, and a heap given as argument.

Raises:

  • ArgumentError, if given object is not a heap

Parameters:

Returns:

  • self object



261
262
263
264
 
# File 'lib/algorithmix/data_structure/heap/binary_heap.rb', line 261

def intersect!(binary_heap)
  raise ArgumentError, "Undefined method BinaryHeap#intersect! for #{binary_heap}:#{binary_heap.class}" unless binary_heap.is_a?(BinaryHeap)
  from_obj(@container & binary_heap.to_a, false)
end

#length ⇒ Object

Returns number of elements in the heap.



74
75
76
 
# File 'lib/algorithmix/data_structure/heap/binary_heap.rb', line 74

def length
  @container.size
end

#map(&block) ⇒ BinaryHeap

Applies a function to each element of the heap.

Parameters:

Returns:

  • a new binary heap



371
372
373
 
# File 'lib/algorithmix/data_structure/heap/binary_heap.rb', line 371

def map(&block)
  BinaryHeap.new(@container.map { |e| block.call(e)}, min: !@max)
end

#map!(&block) ⇒ BinaryHeap

Applies a function to each element of the heap.

Parameters:

Returns:

  • self object



379
380
381
 
# File 'lib/algorithmix/data_structure/heap/binary_heap.rb', line 379

def map!(&block)
  from_obj(@container.map { |e| block.call(e)}, false)
end

#merge(binary_heap) ⇒ BinaryHeap

Concatenates contents of the heap, and a heap given as argument.

Raises:

  • ArgumentError, if given object is not a heap

Parameters:

Returns:

  • a new binary heap



189
190
191
192
 
# File 'lib/algorithmix/data_structure/heap/binary_heap.rb', line 189

def merge(binary_heap)
  raise ArgumentError, "Undefined method BinaryHeap#merge for #{binary_heap}:#{binary_heap.class}" unless binary_heap.is_a?(BinaryHeap)
  self + binary_heap
end

#merge!(binary_heap) ⇒ BinaryHeap

Concatenates contents of the heap, and a heap given as argument.

Raises:

  • ArgumentError, if given object is not a heap

Parameters:

Returns:

  • self object



209
210
211
212
 
# File 'lib/algorithmix/data_structure/heap/binary_heap.rb', line 209

def merge!(binary_heap)
  raise ArgumentError, "Undefined method BinaryHeap#merge! for #{binary_heap}:#{binary_heap.class}" unless binary_heap.is_a?(BinaryHeap)
  from_obj(@container + binary_heap.to_a, false)
end

#select(&block) ⇒ BinaryHeap

Filters elements of the heap by given condition.

Parameters:

Returns:

  • a new binary heap



335
336
337
 
# File 'lib/algorithmix/data_structure/heap/binary_heap.rb', line 335

def select(&block)
  BinaryHeap.new(@container.select { |e| block.call(e)}, min: !@max)
end

#select!(&block) ⇒ BinaryHeap

Filters elements of the heap by given condition.

Parameters:

Returns:

  • self object



343
344
345
 
# File 'lib/algorithmix/data_structure/heap/binary_heap.rb', line 343

def select!(&block)
  from_obj(@container.select { |e| block.call(e)}, false)
end

#size ⇒ Object

Returns number of elements in the heap.



69
70
71
 
# File 'lib/algorithmix/data_structure/heap/binary_heap.rb', line 69

def size
  @container.size
end

#symmetric_difference(binary_heap) ⇒ BinaryHeap

Finds the symmetric difference of contents of the heap, and a heap given as argument.

Raises:

  • ArgumentError, if given object is not a heap

Parameters:

Returns:

  • a new binary heap



304
305
306
307
 
# File 'lib/algorithmix/data_structure/heap/binary_heap.rb', line 304

def symmetric_difference(binary_heap)
  raise ArgumentError, "Undefined method BinaryHeap#symmetric_difference for #{binary_heap}:#{binary_heap.class}" unless binary_heap.is_a?(BinaryHeap)
  self ^ binary_heap
end

#symmetric_difference!(binary_heap) ⇒ BinaryHeap

Finds the symmetric difference of contents of the heap, and a heap given as argument.

Raises:

  • ArgumentError, if given object is not a heap

Parameters:

Returns:

  • self object



314
315
316
317
318
 
# File 'lib/algorithmix/data_structure/heap/binary_heap.rb', line 314

def symmetric_difference!(binary_heap)
  raise ArgumentError, "Undefined method BinaryHeap#symmetric_difference! for #{binary_heap}:#{binary_heap.class}" unless binary_heap.is_a?(BinaryHeap)
  result = (@container | binary_heap.to_a) - (@container & binary_heap.to_a)
  from_obj(result, false)
end

#to_a ⇒ Object

Converts content of the heap to an array.



321
322
323
 
# File 'lib/algorithmix/data_structure/heap/binary_heap.rb', line 321

def to_a
  @container
end

#top ⇒ Object

Returns top element of the heap, without removing it.

Returns:

  • top element.



64
65
66
 
# File 'lib/algorithmix/data_structure/heap/binary_heap.rb', line 64

def top
  @container.first
end

#union(binary_heap) ⇒ BinaryHeap

Unites contents of the heap, and a heap given as argument.

Raises:

  • ArgumentError, if given object is not a heap

Parameters:

Returns:

  • a new binary heap



225
226
227
228
 
# File 'lib/algorithmix/data_structure/heap/binary_heap.rb', line 225

def union(binary_heap)
  raise ArgumentError, "Undefined method BinaryHeap#union for #{binary_heap}:#{binary_heap.class}" unless binary_heap.is_a?(BinaryHeap)
  self | binary_heap
end

#union!(binary_heap) ⇒ BinaryHeap

Unites contents of the heap, and a heap given as argument.

Raises:

  • ArgumentError, if given object is not a heap

Parameters:

Returns:

  • self object



235
236
237
238
 
# File 'lib/algorithmix/data_structure/heap/binary_heap.rb', line 235

def union!(binary_heap)
  raise ArgumentError, "Undefined method BinaryHeap#union! for #{binary_heap}:#{binary_heap.class}" unless binary_heap.is_a?(BinaryHeap)
  from_obj(@container | binary_heap.to_a, false)
end

#|(binary_heap) ⇒ BinaryHeap

Unites contents of the heap, and a heap given as argument.

Raises:

  • ArgumentError, if given object is not a heap

Parameters:

Returns:

  • a new binary heap



219
220
221
222
 
# File 'lib/algorithmix/data_structure/heap/binary_heap.rb', line 219

def |(binary_heap)
  raise ArgumentError, "Undefined method BinaryHeap#| for #{binary_heap}:#{binary_heap.class}" unless binary_heap.is_a?(BinaryHeap)
  BinaryHeap.new(@container | binary_heap.to_a, min: !@max)
end