class Algorithmix::DataStructure::Heap::BinaryHeap

Public Class Methods

new(obj = nil, copy: false, min: false) click to toggle source

Creates a new binary heap.

@param obj [#to_a] can be any object, which responds to to_a method. By default is set to nil. @kwarg copy [true, false] if is set to true, content of the object will be copied into content of the new heap.

By default is set to false.

@kwarg min [true, false] defines the type of the new heap, be default min is set to false @raise ArgumentError, if given object doesn't respond to to_a method. @return [BinaryHeap] a newly created binary heap

# 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

Public Instance Methods

!=(binary_heap) click to toggle source

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

@param binary_heap [BinaryHeap] @raise ArgumentError, if given object is not a heap. @return [true, false] false if heaps are equal, true otherwise

# 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) click to toggle source

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

@param binary_heap [BinaryHeap] @raise ArgumentError, if given object is not a heap @return [BinaryHeap] a new binary heap

# 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) click to toggle source

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

@param binary_heap [BinaryHeap] @raise ArgumentError, if given object is not a heap @return [BinaryHeap] a new binary heap

# 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) click to toggle source

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

@param binary_heap [BinaryHeap] @raise ArgumentError, if given object is not a heap @return [BinaryHeap] a new binary heap

# 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) click to toggle source

(see insert)

# File lib/algorithmix/data_structure/heap/binary_heap.rb, line 45
def <<(value)
  insert(value)
end
<=>(binary_heap) click to toggle source

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

@param binary_heap [BinaryHeap] @raise ArgumentError, if given object is not a heap. @return

> 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

# 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) click to toggle source

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

@param binary_heap [BinaryHeap] @raise ArgumentError, if given object is not a heap. @return [true, false] true if heaps are equal, false otherwise

# 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) click to toggle source

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

@param binary_heap [BinaryHeap] @raise ArgumentError, if given object is not a heap @return [BinaryHeap] a new binary heap

# 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) click to toggle source

(see map)

# File lib/algorithmix/data_structure/heap/binary_heap.rb, line 384
def apply(&block)
  map(&block)
end
apply!(&block) click to toggle source

(see map!)

# File lib/algorithmix/data_structure/heap/binary_heap.rb, line 389
def apply!(&block)
  map!(&block)
end
assign(obj, copy: false) click to toggle source

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

@param obj [#to_a] can be any object, which responds to to_a method. By default is set to nil. @kwarg copy [true, false] if is set to true, content of the object will be copied into content of the new heap.

By default is set to false.

@raise ArgumentError, if given object doesn't respond to to_a method. @return [BinaryHeap] self object

# File lib/algorithmix/data_structure/heap/binary_heap.rb, line 30
def assign(obj, copy: false)
  from_obj(obj, copy)
end
clear() click to toggle source

Clears content of the heap.

# File lib/algorithmix/data_structure/heap/binary_heap.rb, line 326
def clear
  @container = []
  self
end
concat(binary_heap) click to toggle source

(see +)

# 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) click to toggle source

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

@param binary_heap [BinaryHeap] @raise ArgumentError, if given object is not a heap @return [BinaryHeap] self object

# 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) click to toggle source

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

@kwarg idx [Integer] any integer, which can represent index at an array. @krarg old_value @kwarg new_value @raise TypeError, if current heap has type max heap @raise ArgumentError, if idx or old_value are not provided @raise ArgumentError, if new_value is not provided @return [BinaryHeap] self object

# 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) click to toggle source

(see #!=)

# 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) click to toggle source

(see -)

# 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) click to toggle source

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

@param binary_heap [BinaryHeap] @raise ArgumentError, if given object is not a heap @return [BinaryHeap] self object

# 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?() click to toggle source

Returns information for current …

# File lib/algorithmix/data_structure/heap/binary_heap.rb, line 79
def empty?
  @container.empty?
end
eql?(binary_heap) click to toggle source

(see #==)

# 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() click to toggle source

Removes top element of the heap.

@raise Algorithmix::EmptyContainerError, if the heap is empty. @return top element of the heap.

# 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) click to toggle source

(see select)

# File lib/algorithmix/data_structure/heap/binary_heap.rb, line 348
def filter(&block)
  select(&block)
end
filter!(&block) click to toggle source

(see select!)

# File lib/algorithmix/data_structure/heap/binary_heap.rb, line 353
def filter!(&block)
  select!(&block)
end
find_all(&block) click to toggle source

(see select)

# File lib/algorithmix/data_structure/heap/binary_heap.rb, line 358
def find_all(&block)
  select(&block)
end
find_all!(&block) click to toggle source

(see select!)

# 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) click to toggle source

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

@kwarg idx [Integer] any integer, which can represent index at an array. @krarg old_value @kwarg new_value @raise TypeError, if current heap has type min heap @raise ArgumentError, if idx or old_value are not provided @raise ArgumentError, if new_value is not provided @return [BinaryHeap] self object

# 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) click to toggle source

Inserts a value in the heap.

@param value @return [BinaryHeap] self object

# 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) click to toggle source

(see #&)

# 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) click to toggle source

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

@param binary_heap [BinaryHeap] @raise ArgumentError, if given object is not a heap @return [BinaryHeap] self object

# 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() click to toggle source

(see size)

# File lib/algorithmix/data_structure/heap/binary_heap.rb, line 74
def length
  @container.size
end
map(&block) click to toggle source

Applies a function to each element of the heap.

@param block @return [BinaryHeap] a new binary heap

# 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) click to toggle source

Applies a function to each element of the heap.

@param block @return [BinaryHeap] self object

# 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) click to toggle source

(see +)

# 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) click to toggle source

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

@param binary_heap [BinaryHeap] @raise ArgumentError, if given object is not a heap @return [BinaryHeap] self object

# 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) click to toggle source

Filters elements of the heap by given condition.

@param block @return [BinaryHeap] a new binary heap

# 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) click to toggle source

Filters elements of the heap by given condition.

@param block @return [BinaryHeap] self object

# 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() click to toggle source

Returns number of elements in the heap.

# File lib/algorithmix/data_structure/heap/binary_heap.rb, line 69
def size
  @container.size
end
symmetric_difference(binary_heap) click to toggle source

(see #^)

# 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) click to toggle source

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

@param binary_heap [BinaryHeap] @raise ArgumentError, if given object is not a heap @return [BinaryHeap] self object

# 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() click to toggle source

Converts content of the heap to an array.

# File lib/algorithmix/data_structure/heap/binary_heap.rb, line 321
def to_a
  @container
end
top() click to toggle source

Returns top element of the heap, without removing it.

@return top element.

# File lib/algorithmix/data_structure/heap/binary_heap.rb, line 64
def top
  @container.first
end
union(binary_heap) click to toggle source

(see #|)

# 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) click to toggle source

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

@param binary_heap [BinaryHeap] @raise ArgumentError, if given object is not a heap @return [BinaryHeap] self object

# 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) click to toggle source

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

@param binary_heap [BinaryHeap] @raise ArgumentError, if given object is not a heap @return [BinaryHeap] a new binary heap

# 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

Private Instance Methods

build_heap() click to toggle source
# File lib/algorithmix/data_structure/heap/binary_heap.rb, line 429
def build_heap
  (@container.length / 2).downto(0) do |idx|
    heapify(idx)
  end
end
change_key(idx, value, increase: false) click to toggle source
# File lib/algorithmix/data_structure/heap/binary_heap.rb, line 446
def change_key(idx, value, increase: false)
  idx = idx < 0 ? idx + @container.size : idx
  @container[idx] = increase ? (@container[idx] < value ? value : @container[idx]) :
                               (@container[idx] > value ? value : @container[idx])

  sift_up(idx)
end
from_obj(obj, copy) click to toggle source
# File lib/algorithmix/data_structure/heap/binary_heap.rb, line 395
def from_obj(obj, copy)
  raise ArgumentError, "Object doesn't respond to #to_a method" unless obj.respond_to?(:to_a)
  @container = copy ? obj.send(:to_a).dup : obj.send(:to_a)

  build_heap
  self
end
heapify(idx) click to toggle source
# File lib/algorithmix/data_structure/heap/binary_heap.rb, line 403
def heapify(idx)
  return if idx.nil?
  lhs = idx * 2 + 1
  rhs = idx * 2 + 2
  current = idx

  if !@container[lhs].nil? &&
    ((@max && @container[lhs] > @container[current]) ||
    (!@max && @container[lhs] < @container[current]))

    current = lhs
  end

  if !@container[rhs].nil? &&
    ((@max && @container[rhs] > @container[current]) ||
    (!@max && @container[rhs] < @container[current]))

    current = rhs
  end

  if current != idx
    @container[idx], @container[current] = @container[current], @container[idx]
    heapify(current)
  end
end
sift_up(idx) click to toggle source
# File lib/algorithmix/data_structure/heap/binary_heap.rb, line 435
def sift_up(idx)
  return if idx.zero?
  parent = idx.even? ? idx / 2 - 1 : idx / 2

  if (@max && @container[parent] < @container[idx]) || (!@max && @container[parent] > @container[idx])
    @container[parent], @container[idx] = @container[idx], @container[parent]

    sift_up(parent)
  end
end